Tree
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Solution
1export class BinaryTreeNode<T> {
2 public value: T;
3 public left: BinaryTreeNode<T> | null;
4 public right: BinaryTreeNode<T> | null;
5
6 /**
7 * Initialize a Binary Tree node.
8 * @param {T} value The value of the node.
9 */
10 constructor(value?: T) {
11 if (value === undefined) throw new Error("Value cannot be undefined");
12 this.value = value;
13 this.left = null;
14 this.right = null;
15 }
16}
17
18export class BinaryTree<T> {
19 root: BinaryTreeNode<T> | null = null;
20 /**
21 * Initialize the Binary Tree.
22 * @param {T} value The value of the root node.
23 */
24 constructor(value?: T) {
25 if (value !== undefined) this.root = new BinaryTreeNode(value);
26 }
27
28 /**
29 * Get the number of nodes in the tree.
30 * @return {number} The number of nodes in the tree.
31 */
32 size(): number {
33 function _size(node: BinaryTreeNode<T> | null): number {
34 if (!node) return 0;
35 return 1 + _size(node.left) + _size(node.right);
36 }
37 return this.root ? _size(this.root) : 0;
38 }
39
40 /**
41 * Get the height of the tree.
42 * @return {number} The height of the tree.
43 */
44 height(): number {
45 function _height(node: BinaryTreeNode<T> | null): number {
46 if (!node) return -1;
47 return 1 + Math.max(_height(node.left), _height(node.right));
48 }
49 return this.root ? _height(this.root) : 0;
50 }
51
52 /**
53 * Traverse the tree in an in-order fashion.
54 * @return {Array<T>} An array of values of the nodes in in-order traversal.
55 */
56 inOrder(): Array<T> {
57 const arr: Array<T> = [];
58 function dfs(node: BinaryTreeNode<T> | null): void {
59 if (!node) return;
60 dfs(node.left);
61 arr.push(node.value);
62 dfs(node.right);
63 }
64 dfs(this.root);
65 return arr;
66 }
67
68 /**
69 * Traverse the tree in a pre-order fashion.
70 * @return {Array<T>} An array of values of the nodes in pre-order traversal.
71 */
72 preOrder(): Array<T> {
73 const arr: Array<T> = [];
74 function dfs(node: BinaryTreeNode<T> | null): void {
75 if (!node) return;
76 arr.push(node.value);
77 dfs(node.left);
78 dfs(node.right);
79 }
80 dfs(this.root);
81 return arr;
82 }
83
84 /**
85 * Traverse the tree in a post-order fashion.
86 * @return {Array<T>} An array of values of the nodes in post-order traversal.
87 */
88 postOrder(): Array<T> {
89 const arr: Array<T> = [];
90 function dfs(node: BinaryTreeNode<T> | null): void {
91 if (!node) return;
92 dfs(node.left);
93 dfs(node.right);
94 arr.push(node.value);
95 }
96 dfs(this.root);
97 return arr;
98 }
99
100 /**
101 * Checks if the binary tree is balanced, i.e. depth of the two subtrees of
102 * every node never differ by more than 1.
103 * @return {boolean}
104 */
105 isBalanced(): boolean {
106 function dfs(node: BinaryTreeNode<T> | null): number {
107 if (!node) return 0;
108 const left_height = dfs(node.left);
109 const right_height = dfs(node.right);
110 if (
111 left_height === -1 ||
112 right_height === -1 ||
113 Math.abs(left_height - right_height) > 1
114 )
115 return -1;
116 return 1 + Math.max(left_height, right_height);
117 }
118 return dfs(this.root) !== -1;
119 }
120
121 /**
122 * Checks if the binary tree is complete, i.e., all levels are completely filled except possibly the last level,
123 * which is filled from left to right.
124 * @return {boolean} True if the binary tree is complete, false otherwise.
125 */
126 isComplete(): boolean {
127 if (!this.root) return true;
128 const queue: Array<BinaryTreeNode<T> | null> = [this.root];
129 let found_null = false;
130 while (queue.length > 0) {
131 const node = queue.shift();
132 if (node == null) {
133 found_null = true;
134 } else {
135 if (found_null) return false;
136 queue.push(node.left);
137 queue.push(node.right);
138 }
139 }
140 return true;
141 }
142}
143