© Sammie Bae 2019
Sammie BaeJavaScript Data Structures and Algorithmshttps://doi.org/10.1007/978-1-4842-3988-9_15

15. Trees

Sammie Bae1 
(1)
Hamilton, ON, Canada
 

A general tree data structure is composed of nodes with children nodes. The first/top node is called the root node . This chapter will explore many different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this chapter will cover what trees are and how they are structured. Then, it will cover methods of traversing the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store easily searchable data.

General Tree Structure

A general tree data structure looks like Figure 15-1 when it can have any number of children.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig1_HTML.jpg
Figure 15-1

Generalized tree with any number of children

The code block for the node in the Figure 15-1 tree is as follows:
1   function TreeNode(value){
2       this.value = value;
3       this.children = [];
4   }

Binary Trees

A binary tree is a type of tree that has only two children nodes: left and right. See the following code and Figure 15-2:
1   function BinaryTreeNode(value) {
2       this.value = value;
3       this.left = null;
4       this.right = null;
5   }
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig2_HTML.jpg
Figure 15-2

Binary tree

A binary tree always has a root node (the node at the top), which is initialized to null before any element is inserted.
1   function BinaryTree(){
2       this._root = null;
3   }

Tree Traversal

Traversal through an array is simple: you access the tree using the index and increment the index until the index reaches the size limit. With trees, the left and right pointers have to be followed in order to go through every element in the tree. There are various ways to do this, of course; the most popular traversal techniques are pre-order traversal, post-order traversal, in-order traversal, and level-order traversal.

All the code for tree traversals is available on GitHub.1

Pre-order Traversal

Pre-order traversal visits nodes in the following order: root (the current node), left, right. In Figure 15-3, you can see that 42 is the root, so it’s visited first. Then it goes left; at this point, the left of the parent (41) is now considered the new root. This new root (41) is printed; then it goes left again to 10. So, 10 is set to the new root but cannot continue without a child. Then 40 is visited because that is the right of the previous parent (41). This process continues, and the whole order is denoted by the gray squares in Figure 15-3.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig3_HTML.jpg
Figure 15-3

Pre-order traversal

Recursively, this is implemented easily. The base case terminates when the node is null. Otherwise, it prints the node value and then calls the recursive function on its left child and then its right child.
 1   BinaryTree.prototype.traversePreOrder = function() {
 2       traversePreOrderHelper(this._root);
 3
 4       function traversePreOrderHelper(node) {
 5           if (!node)
 6               return;
 7           console.log(node.value);
 8           traversePreOrderHelper(node.left);
 9           traversePreOrderHelper(node.right);
10       }
11   }
This can also be done iteratively, but it is harder to implement .
 1   BinaryTree.prototype.traversePreOrderIterative = function() {
 2       //create an empty stack and push root to it
 3       var nodeStack = [];
 4       nodeStack.push(this._root);
 5
 6       //  Pop all items one by one. Do following for every popped item
 7       //   a) print it
 8       //   b) push its right child
 9       //   c) push its left child
10       // Note that right child is pushed first so that left
11       // is processed first */
12       while (nodeStack.length) {
13           //# Pop the top item from stack and print it
14           var node = nodeStack.pop();
15           console.log(node.value);
16
17           //# Push right and left children of the popped node to stack
18           if (node.right)
19               nodeStack.push(node.right);
20           if (node.left)
21               nodeStack.push(node.left);
22       }
23   }

Here is the result: [42, 41, 10, 40, 50, 45, 75].

In-Order Traversal

In-order traversal visits nodes in the following order: left, root (current node), right. For the tree shown in Figure 15-4, the gray squares indicate the in-order traversal order. As you can see, 10 (the leftmost node) is printed first, and 7 (the rightmost node) is printed last.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig4_HTML.jpg
Figure 15-4

In-order traversal

In-order traversal is also implemented easily with recursion . The base case is when a node is null. In the nonbase case, it calls the recursive function on the left child, prints the current node, and then calls the recursive function on the right child.
 1   BinaryTree.prototype.traverseInOrder = function() {
 2       traverseInOrderHelper(this._root);
 3
 4       function traverseInOrderHelper(node) {
 5           if (!node)
 6               return;
 7           traverseInOrderHelper(node.left);
 8           console.log(node.value);
 9           traverseInOrderHelper(node.right);
10       }
11   }
12
13   BinaryTree.prototype.traverseInOrderIterative = function() {
14       var current = this._root,
15           s = [],
16           done = false;
17
18       while (!done) {
19           // Reach the left most Node of the current Node
20           if (current != null) {
21               // Place pointer to a tree node on the stack
22               // before traversing the node's left subtree
23               s.push(current);
24               current = current.left;
25           } else {
26               if (s.length) {
27                   current = s.pop();
28                   console.log(current.value);
29                   current = current.right;
30               } else {
31                   done = true;
32               }
33           }
34       }
35   }

Here is the result of this traversal : [10, 41, 40, 42, 45, 50, 75].

Post-order Traversal

Post-order traversal visits nodes in the following order : left, right, root (the current node). For the tree shown in Figure 15-5, the gray squares indicate the in-order traversal order. As you can see, 10 (the leftmost node) is printed first, and 42 (the root node) is printed last.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig5_HTML.jpg
Figure 15-5

Post-order traversal

Here’s the code:
 1   BinaryTree.prototype.traversePostOrder = function() {
 2       traversePostOrderHelper(this._root);
 3
 4       function traversePostOrderHelper(node) {
 5           if (node.left)
 6               traversePostOrderHelper(node.left);
 7           if (node.right)
 8               traversePostOrderHelper(node.right);
 9           console.log(node.value);
10       }
11   }
12
13   BinaryTree.prototype.traversePostOrderIterative = function() {
14       // Create two stacks
15       var s1 = [],
16           s2 = [];
17
18       // Push root to first stack
19           s1.push(this._root);
20
21       //# Run while first stack is not empty
22       while (s1.length) {
23           // Pop an item from s1 and append it to s2
24           var node = s1.pop();
25           s2.push(node);
26
27           // Push left and right children of removed item to s1
28           if (node.left)
29               s1.push(node.left);
30           if (node.right)
31               s1.push(node.right);
32       }
33       // Print all elements of second stack
34       while (s2.length) {
35           var node = s2.pop();
36           console.log(node.value);
37       }
38   }

Here is the result : [10, 40, 41, 45, 75, 50, 42].

Level-Order Traversal

Level-order traversal , illustrated in Figure 15-6, is also known as breadth first search (BFS).
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig6_HTML.jpg
Figure 15-6

Level-order traversal

More of this will be covered in Chapter 17, but this method essentially visits each node level by level instead of going deep into the left or right.
 1   BinaryTree.prototype.traverseLevelOrder = function() {
 2       // Breath first search
 3       var root = this._root,
 4           queue = [];
 5
 6       if (!root)
 7           return;
 8       queue.push(root);
 9
10       while (queue.length) {
11           var temp = queue.shift();
12           console.log(temp.value);
13           if (temp.left)
14               queue.push(temp.left);
15           if (temp.right)
16               queue.push(temp.right);
17       }
18   }

Here is the result: [42, 41, 50, 10, 40, 45, 75].

Tree Traversal Summary

If you know you need to explore the roots before inspecting any leaves, choose pre-order traversal because you will encounter all the roots before all of the leaves.

If you know you need to explore all the leaves before any nodes, choose post-order traversal because you don’t waste any time inspecting roots when searching for leaves.

If you know that the tree has an inherent sequence in the nodes and you want to flatten the tree into its original sequence, then you should use an in-order traversal. The tree would be flattened in the same way it was created. A pre-order or post-order traversal might not unwind the tree back into the sequence that was used to create it.

Time Complexity: O(n)

The time complexity of any of these traversals is the same because each traversal requires that all nodes are visited.

Binary Search Trees

Binary search trees (BSTs) also have two children, left and right. However, in a binary search tree, the left child is smaller than the parent, and the right child is bigger than the parent. BSTs have this structure because this property enables for searching, inserting, and removing specific values with O(log2(n)) time complexity.

Figure 15-7 shows the BST property. 1 is smaller than 2, so it is the left child of 2, and since 3 is bigger than 3, it is the right child of 2.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig7_HTML.jpg
Figure 15-7

Binary search tree

Binary search trees have a root node (the topmost node), which is originally initialized null (before any item is inserted).
1   function BinarySearchTree(){
2       this._root = null;
3   }
Figure 15-7 also shows a balanced binary search tree where the height is minimized by having children on both the left and right sides. However, Figure 15-8 shows an unbalanced tree where children are only to the right of the parent. This has significant impact on the data structure and increases the time complexity of insertion, deletion, and search from O(log2(n)) to O(n). The height of a perfect balanced tree is log2(n), while an unbalanced tree can be n in the worst case.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig8_HTML.jpg
Figure 15-8

Unbalanced binary search tree

Insertion

Inserting into the BST requires a couple of steps. First, if the root is empty, the root becomes the new node. Otherwise, a while loop is used to traverse the BST until the right condition is met. At each loop iteration, it is checked whether the new node is greater or smaller than the currentRoot.
 1   BinarySearchTree.prototype.insert =  function(value) {
 2       var thisNode = {left: null, right: null, value: value};
 3       if(!this._root){
 4           //if there is no root value yet
 5           this._root = thisNode;
 6       }else{
 7           //loop traverse until
 8           var currentRoot = this._root;
 9           while(true){
10               if(currentRoot.value>value){
11                   //let's increment if it's not a null and insert if it is a null
12                   if(currentRoot.left!=null){
13                       currentRoot = currentRoot.left;
14                   }else{
15                       currentRoot.left = thisNode;
16                       break;
17                   }
18               } else if (currentRoot.value<value){
19                   //if bigger than current, put it on the right
20                   //let's increment if it's not a null and insert if it is a null
21                   if(currentRoot.right!=null){
22                       currentRoot = currentRoot.right;
23                   }else{
24                       currentRoot.right = thisNode;
25                       break;
26                   }
27               } else {
28                   //case that both are the same
29                   break;
30               }
31           }
32       }
33   }

Time Complexity (for balanced trees): O(log2(n))

Time Complexity (for unbalanced trees): O(n)

Time complexity is dependent on the height of the binary search tree.

Deletion

This algorithm works by first traversing down the tree looking specifically for the node with the specified value. When the node is found, there are three possible cases:

  • Case 1: The node has no children.

    This is the simplest case. If the node has no child, return null. That node has been deleted now.

  • Case 2: The node has one child.

    If the node has one child, simply return the existing child. That child has now bubbled up and replaced the parent.

  • Case 3: The node has two children.

    If the node has two children, either find the maximum of the left subtree or find the minimum of the right subtree to replace that node.

The following code implements the described three cases. First, it traverses recursively until one of those cases is met, and then the node is removed.
 1   BinarySearchTree.prototype.remove = function(value) {
 2
 3       return deleteRecursively(this._root, value);
 4
 5       function deleteRecursively(root, value) {
 6           if (!root) {
 7               return null;
 8           } else if (value < root.value) {
 9               root.left = deleteRecursively(root.left, value);
10           } else if (value > root.value) {
11               root.right = deleteRecursively(root.right, value);
12           } else {
13               //no child
14               if (!root.left && !root.right) {
15                   return null; // case 1
16               } else if (!root.left) { // case 2
17                   root = root.right;
18                   return root;
19               } else if (!root.right) { // case 2
20                   root = root.left;
21                   return root;
22               } else {
23                   var temp = findMin(root.right); // case 3
24                   root.value = temp.value;
25                   root.right = deleteRecursively(root.right, temp.value);
26                   return root;
27               }
28           }
29           return root;
30       }
31
32       function findMin(root) {
33           while (root.left) {
34               root = root.left;
35           }
36           return root;
37       }
38   }

Time Complexity (for balanced tree): O(log2(n))

Time Complexity (for unbalanced trees): O(n)

Time complexity for deletion is also O(log2(n)) because at most that’s the height that will need to be traversed to find and delete the desired node.

Search

Search can be performed using the property that BST node’s left child is always smaller than its parent and that BST node’s right child is always greater than its parent. Traversing the tree can be done by checking whether currentRoot is smaller or greater than the value to be searched. If currentRoot is smaller, the right child is visited. If currentRoot is bigger, the left child is visited.
 1   BinarySearchTree.prototype.findNode = function(value) {
 2       var currentRoot = this._root,
 3           found = false;
 4       while (currentRoot) {
 5           if (currentRoot.value > value) {
 6               currentRoot = currentRoot.left;
 7           } else if (currentRoot.value < value) {
 8               currentRoot = currentRoot.right;
 9           } else {
10               //we've found the node
11               found = true;
12               break;
13           }
14       }
15       return found;
16   }
17   var bst1 = new BinarySearchTree();
18   bst1.insert(1);
19   bst1.insert(3);
20   bst1.insert(2);
21   bst1.findNode(3); // true
22   bst1.findNode(5); // false

Time Complexity (for balanced tree): O(log2(n))

Time Complexity (for unbalanced trees): O(n)

Note that all of the operations’ time complexities are equal to the height of the binary tree search. With unbalanced binary search trees, the time complexity is high. To address this, there are families of binary search trees that ensure the height is balanced. One example of such self-balancing trees is an AVL tree.

AVL Trees

AVL is a binary search tree that balances itself; it’s named after the inventors Georgy Adelson-Velsky and Evgenii Landis. An AVL tree keeps the BST height to a minimum and ensures O(log2(n)) time complexities for search, insertion, and deletion. In previous examples, we defined both TreeNode and a Tree class and set the root of Tree as a TreeNode class. However, for the AVL tree implementation, only the AVLTree class, which represents the node of the AVL tree, will be used for the simplification of the code.
 1   function AVLTree (value) {
 2       this.left = null;
 3       this.right = null;
 4       this.value = value;
 5       this.depth = 1;
 6   }
The height of the AVL tree is based on the height of the children and can be calculated using the following code block:
 1   AVLTree.prototype.setDepthBasedOnChildren = function() {
 2       if (this.node == null) {
 3           this.depth = 0;
 4       } else {
 5           this.depth = 1;
 6       }
 7
 8       if (this.left != null) {
 9           this.depth = this.left.depth + 1;
10       }
11       if (this.right != null && this.depth <= this.right.depth) {
12           this.depth = this.right.depth + 1;
13       }
14   }

Single Rotation

AVL trees rotate their children to maintain balance after insertion.

Rotate Left

Here is an example of when a node has to rotate left. Node 40’s children, the 45 and 47 nodes, cause the height to be unbalanced, as shown in Figure 15-9. The 45 becomes the parent node in Figure 15-10 to balance the BST.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig9_HTML.jpg
Figure 15-9

Rotate left before

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig10_HTML.jpg
Figure 15-10

Rotate left after

To perform a left rotation, first get the left child and store it. This is the “original” left child. The original left child is to be the parent of the node now. Set the node’s left child to be the original left child’s left child. Finally, set the right child of the original left child to be the node.
 1   AVLTree.prototype.rotateLL = function() {
 2
 3       var valueBefore = this.value;
 4       var rightBefore = this.right;
 5       this.value = this.left.value;
 6
 7       this.right = this.left;
 8       this.left = this.left.left;
 9       this.right.left = this.right.right;
10       this.right.right = rightBefore;
11       this.right.value = valueBefore;
12
13       this.right.getDepthFromChildren();
14       this.getDepthFromChildren();
15   };

Rotate Right

Here is an example of when a node has to rotate right. 60’s children, the 55 and 52 nodes, cause the height to be unbalanced, as shown in Figure 15-11. The 55 node becomes the parent in Figure 15-12 to balance the BST.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig11_HTML.jpg
Figure 15-11

Rotate right before

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig12_HTML.jpg
Figure 15-12

Rotate right after

To implement this previously described algorithm, first get the left child and store it. This the original left child. The original left child is to be the parent of the node now. Set the node’s left child to be the original left child’s left child. Finally, set the right child of the original left child to be the node.
 1   AVLTree.prototype.rotateRR = function() {
 2       // the right side is too long => rotate from the right (_not_ rightwards)
 3       var valueBefore = this.value;
 4       var leftBefore = this.left;
 5       this.value = this.right.value;
 6
 7       this.left = this.right;
 8       this.right = this.right.right;
 9       this.left.right = this.left.left;
10       this.left.left = leftBefore;
11       this.left.value = valueBefore;
12
13       this.left.updateInNewLocation();
14       this.updateInNewLocation();
15   }

Double Rotation

If an AVL tree is still unbalanced after one rotation, it has to rotate twice for full balance.

Rotate Right Left (Right Then Left)

In this example, Figure 15-13 shows a BST where the height is 3. By rotating right and then left, as shown in Figure 15-14 and Figure 15-15, balance is achieved.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig13_HTML.jpg
Figure 15-13

A situation where rotating right and then rotating left is appropriate

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig14_HTML.jpg
Figure 15-14

Rotate right first

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig15_HTML.jpg
Figure 15-15

Rotate left after

Rotate Left Right (Left Then Right)

Similarly, in this example, Figure 15-16 shows a BST where the height is 3. By rotating left and then right, as shown in Figure 15-17 and Figure 15-18, balance is achieved.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig16_HTML.jpg
Figure 15-16

A situation where rotating left and then rotating right is appropriate

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig17_HTML.jpg
Figure 15-17

Rotate left first

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig18_HTML.jpg
Figure 15-18

Rotate right after

Balancing the Tree

To check for balance of the AVL tree, it is a simple comparison of the left and right children’s heights. If the heights are not balanced, rotations are needed. When left is bigger than right, left rotation is done. When right is bigger than left, right rotation is done.
 1   AVLTree.prototype.balance = function() {
 2       var ldepth = this.left == null ? 0 : this.left.depth;
 3       var rdepth = this.right == null ? 0 : this.right.depth;
 4
 5       if (ldepth > rdepth + 1) {
 6       // LR or LL rotation
 7           var lldepth = this.left.left == null ? 0 : this.left.left.depth;
 8           var lrdepth = this.left.right == null ? 0 : this.left.right.depth;
 9
10           if (lldepth < lrdepth) {
11               // LR rotation consists of a RR rotation of the left child
12               this.left.rotateRR();
13               // plus a LL rotation of this node, which happens anyway
14           }
15           this.rotateLL();
16       } else if (ldepth + 1 < rdepth) {
17           // RR or RL rorarion
18           var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
19           var rldepth = this.right.left == null ? 0 : this.right.left.depth;
20
21           if (rldepth > rrdepth) {
22               // RR rotation consists of a LL rotation of the right child
23               this.right.rotateLL();
24               // plus a RR rotation of this node, which happens anyway
25           }
26           this.rotateRR();
27       }
28   }

Insertion

Insertion in AVL BST is the same as the insertion in normal BST except that, once inserted, the parent must balance its children and set the right depth.
 1   AVLTree.prototype.insert = function(value) {
 2       var childInserted = false;
 3       if (value == this.value) {
 4           return false; // should be all unique
 5       } else if (value < this.value) {
 6           if (this.left == null) {
 7               this.left = new AVLTree(value);
 8               childInserted = true;
 9           } else {
10               childInserted = this.left.insert(value);
11               if (childInserted == true) this.balance();
12           }
13       } else if (value > this.value) {
14           if (this.right == null) {
15               this.right = new AVLTree(value);
16               childInserted = true;
17           } else {
18               childInserted = this.right.insert(value);
19
20               if (childInserted == true) this.balance();
21           }
22       }
23       if (childInserted == true) this.setDepthBasedOnChildren();
24       return childInserted;
25   }

Time Complexity: O(nlog2(n))

Space Complexity: O(nlog2(n))

Space complexity is from the recursive call stacks in memory.

Deletion

AVL BST is a type of BST, and therefore the deletion function is the same. Adjusting the depths can be done by calling setDepthBasedOnChildren() during traversal.
 1   AVLTree.prototype.remove = function(value) {
 2       return deleteRecursively(this, value);
 3
 4       function deleteRecursively(root, value) {
 5           if (!root) {
 6               return null;
 7           } else if (value < root.value) {
 8               root.left = deleteRecursively(root.left, value);
 9           } else if (value > root.value) {
10               root.right = deleteRecursively(root.right, value);
11           } else {
12               //no child
13               if (!root.left && !root.right) {
14                   return null; // case 1
15               } else if (!root.left) {
16                   root = root.right;
17                   return root;
18               } else if (!root.right) {
19                   root = root.left;
20                   return root;
21               } else {
22                   var temp = findMin(root.right);
23                   root.value = temp.value;
24                   root.right = deleteRecursively(root.right, temp.value);
25                   return root;
26               }
27           }
28           root.updateInNewLocation(); // ONLY DIFFERENCE from the BST one
29           return root;
30       }
31       function findMin(root) {
32           while (root.left) root = root.left;
33           return root;
34       }
35   }

The time complexity and space complexity are both O(nlog2(n)) because AVL trees are balanced. The space complexity is from the recursive call stacks in memory.

Putting It All Together: AVL Tree Example

With the AVL tree class implemented, Figure 15-19 shows an example of an AVL tree produced by the following code block:
 1   var avlTest = new AVLTree(1,");
 2   avlTest.insert(2);
 3   avlTest.insert(3);
 4   avlTest.insert(4);
 5   avlTest.insert(5);
 6   avlTest.insert(123);
 7   avlTest.insert(203);
 8   avlTest.insert(2222);
 9   console.log(avlTest);
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig19_HTML.jpg
Figure 15-19

AVL result

If a plain binary search tree were used instead, Figure 15-20 shows what it would look like for the same order of insertion.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig20_HTML.jpg
Figure 15-20

BST result

Clearly, this is a skewed binary search tree that is completely unbalanced. At this point, it looks like a linked list. Once the tree becomes completely unbalanced like this, it has a linear time complexity for deletion, insertion, and search instead of logarithmic time.

Summary

Table 15-1 shows the time complexity for each binary search tree operation. Compared to other data structures, the search operation is faster than linked lists, arrays, stacks, and queues. As the name implies, a binary search tree is great for searching elements. However, the insertion and deletion operations are slower, with a time complexity of O(log2(n)) instead of O(1) like a stack or a queue, for example. Furthermore, all operations become O(n) as the tree becomes unbalanced. To ensure the tree stays balanced, self-balancing trees such as a red-black tree or an AVL tree should be used to ensure tree operations have logarithmic time complexity.
Table 15-1

Tree Summary

Operation

Best (If Balanced)

Worst (If Completely Unbalanced)

Deletion

O(log2(n))

O(n)

Insertion

O(log2(n))

O(n)

Search

O(log2(n))

O(n)

Exercises

You can find all the code for the exercises on GitHub.2

FIND THE LOWEST COMMON ANCESTOR OF TWO NODES IN A GIVEN BINARY TREE

The logic for this one is actually fairly simple but hard to notice at first.

If the maximum of the two values is smaller than the current root, go left. If the minimum of the two values is bigger than the current root, go right. Figures 15-21 and 15-22 show the two different cases of this.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig21_HTML.jpg
Figure 15-21

Lowest common ancestor, example 1

../images/465726_1_En_15_Chapter/465726_1_En_15_Fig22_HTML.jpg
Figure 15-22

Lowest common ancestor, example 2

 1   function findLowestCommonAncestor(root, value1, value2) {
 2       function findLowestCommonAncestorHelper(root, value1, value2) {
 3           if (!root)
 4               return;
 5           if (Math.max(value1, value2) < root.value)
 6               return findLowestCommonAncestorHelper(root.left, value1, value2);
 7           if (Math.min(value1, value2) > root.value)
 8               return findLowestCommonAncestorHelper(root.right, value1, value2);
 9           return root.value
10       }
11       return findLowestCommonAncestorHelper(root, value1, value2);
12   }
13   var node1 = {
14       value: 1,
15       left: {
16           value: 0
17       },
18       right: {
19           value: 2
20       }
21   }
22
23   var node2 = {
24       value: 1,
25       left: {
26           value: 0,
27           left: {
28               value: -1
29           },
30           right: {
31               value: 0.5
32           }
33       },
34       right: {
35           value: 2
36       }
37   }
38   console.log(findLowestCommonAncestor(node1, 0, 2)); // 1
39   console.log(findLowestCommonAncestor(node2, 0, 2)); // 1
40   console.log(findLowestCommonAncestor(node1, 0.5, -1)); // 0

Time Complexity: O(log2(n))

PRINT NODES NTH DISTANCE FROM THE ROOT

For this question, traverse the BST in any way (level order was used in this example) and check the height for each BST node to see whether it should be printed.
 1   function printKthLevels(root, k) {
 2       var arrayKth = [];
 3           queue = [];
 4
 5       if (!root) return;
 6
 7       // Breath first search for tree
 8       queue.push([root, 0]);
 9
10       while (queue.length) {
11           var tuple = queue.shift(),
12               temp = tuple[0],
13               height= tuple[1];
14
15           if (height == k) {
16               arrayKth.push(temp.value);
17           }
18           if (temp.left) {
19               queue.push([temp.left, height+1]);
20           }
21           if (temp.right) {
22               queue.push([temp.right,height+1]);
23           }
24       }
25       console.log(arrayKth);
26   }
 1   var node1 = {
 2       value: 1,
 3       left: {
 4           value: 0
 5       },
 6       right: {
 7           value: 2
 8       }
 9   }
10
11   var node2 = {
12       value: 1,
13       left: {
14           value: 0,
15           left: {
16               value: -1
17           },
18           right: {
19               value: 0.5
20           }
21       },
22       right: {
23           value: 2
24       }
25   }
26
27   var node3 = {
28       value: 1,
29      left: {
30           value: 0
31       },
32       right: {
33           value: 2,
34           left: {
35               value: 1.5
36           },
37           right: {
38               value: 3,
39               left: {
40                   value: 3.25
41               }
42           }
43       }
44   }
45
46   printKthLevels(node1, 1); // 1
47   printKthLevels(node1, 2); // [0,2]

CHECK WHETHER A BINARY TREE IS A SUBTREE OF ANOTHER TREE

To do this, traverse the binary tree in any way (I’m choosing to do level order) and check whether the one that it is currently on is the same as the subtree.
 1   function isSameTree(root1, root2) {
 2       if (root1 == null && root2 == null) {
 3           return true;
 4       }
 5       if (root1 == null || root2 == null) {
 6           return false;
 7       }
 8
 9       return root1.value == root2.value &&
10           isSameTree(root1.left, root2.left) &&
11           isSameTree(root1.right, root2.right)
12   }
13
14   function checkIfSubTree(root, subtree) {
15       // Breath first search
16       var queue = [],
17           counter = 0;
18
19       // sanity check for root
20       if (!root) {
21           return;
22       }
23
24       queue.push(root);
25
26       while (queue.length) {
27           var temp = queue.shift();
28
29           if (temp.data == subtree.data == isSameTree(temp, subtree)) {
30               return true;
31           }
32
33           if (temp.left) {
34               queue.push(temp.left);
35           }
36           if (temp.right) {
37               queue.push(temp.right);
38           }
39       }
40       return false;
41   }
42
43   var node1 = {
44       value: 5,
45       left: {
46           value: 3,
47           left: {
48               value: 1
49           },
50           right: {
51               value: 2
52           }
53       },
54       right: {
55           value: 7
56       }
57   }
58
59   var node2 = {
60       value: 3,
61       left: {
62           value: 1
63       },
64       right: {
65           value: 2
66       }
67   }
68
69
70   var node3 = {
71       value: 3,
72       left: {
73           value: 1
74       }
75   }
76
77   console.log(checkIfSubTree(node1, node2)); // true
78   console.log(checkIfSubTree(node1, node3)); // false
79   console.log(checkIfSubTree(node2, node3)); // false

CHECK WHETHER A TREE IS A MIRROR OF ANOTHER TREE

Figure 15-23 shows an example.
../images/465726_1_En_15_Chapter/465726_1_En_15_Fig23_HTML.jpg
Figure 15-23

Mirror trees

Here are three possible cases:

  • Their root node’s key must be the same.

  • The left subtree of root of a and the right subtree root of b are mirrors.

  • The right subtree of a and the left subtree of b are mirrors.

 1   function isMirrorTrees(tree1, tree2) {
 2       // Base case, both empty
 3       if (!tree1 && !tree2) {
 4           return true;
 5       }
 6
 7       // One of them is empty, since only one is empty, not mirrored
 8       if (!tree1 || !tree2) {
 9           return false;
10       }
11
12       // Both non-empty, compare them recursively.
13       // Pass left of one and right of the other
14
15       var checkLeftwithRight = isMirrorTrees(tree1.left, tree2.right),
16           checkRightwithLeft = isMirrorTrees(tree2.right, tree1.left);
17
18       return tree1.value == tree2.value && checkLeftwithRight && checkRightwithLeft;
19   }
20
21   var node1 = {
22       value: 3,
23       left: {
24           value: 1
25       },
26       right: {
27           value: 2
28       }
29   }
30
31   var node2 = {
32       value: 3,
33       left: {
34           value: 2
35       },
36       right: {
37           value: 1
38       }
39   }
40
41   var node3 = {
42       value: 3,
43       left: {
44           value: 1
45       },
46       right: {
47           value: 2,
48           left: {
49               value: 2.5
50           }
51       }
52   }
53
54   console.log(isMirrorTrees(node1, node2)); // true
55   console.log(isMirrorTrees(node2, node3)); // false