The assumption we made here is -- the given tree is balanced, so the height of a N node tree is lgN. We made this assumption for easy analysis of time complexity and space complexity. The tree in its worst case can degenerate into a linked list. The type of the node value is int. The root node could be null. The value of a node can be negative, 0 or positive.
The first thing we have to do is to create a binary tree. Whenever a node gets a job to insert a new value, it delegates the job to either its left child or right child, then waits for the child to finish, then the node updates itself with the new state of its finished child.
Sometimes, the job is mean to be handled by the node itself, then it handles it, returns back to its calling parent. Job done, easy!
public static BTree insert(BTree root, int value) {
if(root == null) {
return new BTree(value, null, null);
}
if(value > root.value) {
root.right = insert(root.right, value);
return root;
}
if(value < root.value) {
root.left = insert(root.left, value);
return root;
}
root.value = value;
return root;
}
The cost of inserting a new node is traveling the height of the tree to reach leaf whose child nodes are null. When the leaf node is reached, the height of the calling stack is the height of the tree, which is lgN for a balanced tree. So the time complexity for inserting the Nth node is O(lgN), the time complexity of building the tree is O(NlgN). The space complexity is O(N) as well since we need to store N extra nodes.
The second thing we do is traversal it. There are 3 basic ways of traversal a binary search tree:
- pre order traversal: recursively visit parent node then visit child nodes.
- in order traversal: recursively visit left child node, then parent node, then right child node.
- post order traversal: recursively visit child nodes, then visit parent node.
//print in order traversal a tree
//print tree element sorted small to large
public static void InOrder(BTree root) {
if(root == null) {
return;
}
InOrder(root.left);
System.out.print(root.value + " ");
InOrder(root.right);
}
The in order traversal ordered the elements in the binary search tree. If you visit left child node, then parent node, then right child node, you visited the tree nodes in ascendent order; if you visit right child node, then parent node, then left child node, you visited the tree nodes in descendent order.
During the traversal, each element is visited once, the time complexity is O(N). We didn't use auxiliary variable during the tree traversal, the space complexity is O(1).
However, the recursive call's stack takes space. It won't start to print until reached the leaf node of the tree. The calling stack's height can reach the tree's height, so the space used by calling stack is O(lgN).
Level order traversal
A little bit harder traversal is level order traversal. If we don't have to detect the layer boundary, breadth-first search with the aid of a queue will work.
During the traversal, each element is visited once, the time complexity is O(N). The elements stored in the queue will take extra space, at the peak, half of the tree elements will be stored in the queue, which is when the lowest layer is enqueued. So the space complexity is also O(N).
Each elements is visited once, the time complexity is O(N). We didn't use auxiliary variable during the tree traversal, the space complexity is O(1). However, the recursive call's stack takes space. It won't start to print until reached the level node of the tree. The calling stack's height can reach the tree's height when it print the lowest layer, the memory it takes is O(lgN).
//print a binary search tree from top down, left to right
public static void LayerOrder(BTree root) {
if(root == null) return;
Queue<BTree> queue = new LinkedList<>();
queue.offer(root);
BTree current = null;
while(!queue.isEmpty()) {
current = queue.poll();
System.out.print(current.value + " ");
if(current.left != null)
queue.offer(current.left);
if(current.right != null)
queue.offer(current.right);
}
}
During the traversal, each element is visited once, the time complexity is O(N). The elements stored in the queue will take extra space, at the peak, half of the tree elements will be stored in the queue, which is when the lowest layer is enqueued. So the space complexity is also O(N).
Traversal layer K nodes
If we have to detect the layer boundary, we need to get the height of the tree k, then iterate k times to print the k layers. Each time, we start from root, recursively visit the root's nodes in the corresponding level in the left and right branch.
/* Print nodes at a given level */
public static void printGivenLevel(BTree root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.value + " ");
else if (level > 1)
{
printGivenLevel(root.left, level-1);
printGivenLevel(root.right, level-1);
}
}
Each elements is visited once, the time complexity is O(N). We didn't use auxiliary variable during the tree traversal, the space complexity is O(1). However, the recursive call's stack takes space. It won't start to print until reached the level node of the tree. The calling stack's height can reach the tree's height when it print the lowest layer, the memory it takes is O(lgN).
Once we understood the above 4 binary search tree traversal, we can easily solve a cluster of problems.
- print tree elements in pre order
- print tree elements in post order
- print tree elements in order
- print tree elements in layer order
- print tree elements in layer order with line break between layers
- print tree elements in ascend order
- print tree elements in descent order
- print tree elements in upside down layer order with line break between layers
- sort a list of number in ascend order
- sort a list of number in descend order
- find the height of a tree
- find the max element in a tree
- find the min element in a tree
- find the size of a tree
- find the sum of the tree elements
- copy a tree
- create a mirror tree of an existing tree (root2.left = root1.right and root2.right = root1.left)
Copy and convert trees
For example:The following example created a binary search tree from an ordered array. It then copied the tree to another tree. It also copied the tree's mirror image to another tree. Then the original tree is converted into the mirror image without creating a new tree. Finally, the trees created in the previous steps are compared.
- creating a tree from an ordered array need to visit each the array element once, the time complexity is O(N). Extra space is needed to create the tree, space complexity is O(N).
- copy a tree need to visit each one of the original tree, the time complexity is O(N). Extra space is needed to create the new tree, space complexity is O(N).
- copy a tree's mirror image to another tree have the same time and space complexity as copying a tree.
- convert a tree to its mirror in place need to visit each node once, the time complexity is O(N), no extra space is needed, the space complexity is O(1).
- For comparing the trees. If 2 trees are not the same, we don't have to visit all the nodes in a tree. If 2 trees are the same, we need to visit each element of a tree, the time complexity is O(N), the space complexity is O(1).
BTree.java
BTreeCopy.javaBTreeCopyTest.java
In the above example, when we want to compare 2 trees, a less efficient way is to traversal one tree pre-order, store the elements in an array, then traversal the other tree pre-order, put the elements in another array, then compare the 2 arrays to decide if the original trees are the same. This approach will traversal the elements 3 times, use 2 extra N sided array to hold the temporary data. Therefore, we traversal the two tree together recursively instead, it takes one one traversal and no auxiliary space needed.
Binary search tree and array duality
Please observe the in-order, pre-order and post-order traversal sequence of the same tree.
1 5 6 9 10 11 12
9 5 1 6 11 10 12
1 6 5 10 12 11 9
- In order traversal sequence is an ordered sequence.
- Pre order traversal sequence has the middle point at the beginning, for the rest of the elements, they are divided into 2 halves. The first half are smaller than middle point, the second half are larger than middle point. Each half is a pre order traversal sequence by itself.
- Post order traversal sequence has the middle point at the end, for the rest of the elements, they are divided into 2 halves. The first half are smaller than middle point, the second half are larger than middle point. Each half is a post order traversal sequence by itself.
Take advantage of the above character, we can solve a cluster of problems:
- re-construct a tree from its post-order sequence array
- re-construct a tree from its pre-order sequence array
- re-construct a tree from its in-order sequence array
- make an array with a binary search tree's in order sequence
- make an array with a binary search tree's pre order sequence
- make an array with a binary search tree's post order sequence
- construct a tree from an ordered array ascent
- construct a tree from an ordered array descent
- store a tree as an array, later reconstruct it
- serialize a tree, store on disc, later reconstruct it
- serialize a tree, transfer on internet, reconstruct it on another host
- compress and decompress a tree
- check if a tree is a binary search tree
- check if an array is qualified as some binary search tree's in order traversal sequence
- check if an array is qualified as some binary search tree's post-order traversal sequence
- check if an array is qualified as some binary search tree's pre-order traversal sequence
- check if an array is the in-order traversal sequence of a given tree
- check if an array is the pre-order traversal sequence of a given tree
- check if an array is the post-order traversal sequence of a given tree
- convert a tree's post-order sequence into pre-order sequence
- convert a tree's pre-order sequence into post-order sequence
- check if two arrays are the same tree's post-order sequence and pre-order sequence
- check if two arrays are the same tree's in-order sequence and post-order sequence
- check if two arrays are the same tree's in-order sequence and pre-order sequence
- construct a tree from an array
