Traversals:
A traversal is a process that visits all the nodes in the tree.
There are two traversal algorithms:
- Depth-First Traversal
- Breadth-First Traversal
Depth-First Traversal
There are 3 kinds of depth-first traversals. All three traversal problems can easily use recursion and divide-and-conquer to solve. But more difficult is to solve them without recursion. Non-recursive methods are mainly focused here:
Preorder Traversal: Visit the parent first and then left and right children
Without Recursion: Take use of stack class in Java. Every time add the value of popped elements to ArrayList first. Then push the right child, then left child.
public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> output = new ArrayList<Integer>(); // Use stack to travere Stack<TreeNode> stack = new Stack<TreeNode>(); // Special case: root is null if (root == null) return output; // Initialize the stack with non-null root stack.push(root); while(!stack.empty()){ TreeNode temp = stack.pop(); // First add the value of popped node output.add(temp.val); // Secondly push the non-null right child if (temp.right != null) stack.push(temp.right); // Thirdly push the non-null left child if (temp.left != null) stack.push(temp.left); } return output; }Inorder Traversal: Visit the left child, then the parent and the right child
Without Recursion: Every time we reach a node v, push all left children recursively into stack. When we reach the left-most child with root at the node v, we add its value to ArrayList and check its right child.
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> output = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode temp = root;
// Remember this condition!!!
while (temp != null || !stack.empty()) {
// Put all left children into stack
while (temp != null){
stack.push(temp);
temp = temp.left;
}
// When a node has no more left child to push
// Add its value and check its right child
temp = stack.pop();
output.add(temp.val);
temp = temp.right;
}
return output;
}
Postorder Traversal: Visit left child, then the right child and then the parent
Without Recursion: Use two references: current for current node, prev for previous visited node.If current is child of prev, means we still have nodes to traverse(push to stack).
If prev is left child of current, means we just finish the traversal of the prev node, we can turn to right subtree.
Else, the current node is ready to add into ArrayList and mark as finished.
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode prev = null; // previously traversed node
TreeNode curr = root;
if (root == null) {
return result;
}
stack.push(root);
while (!stack.empty()) {
curr = stack.peek();
// traverse down the tree
if (prev == null || prev.left == curr || prev.right == curr) {
if (curr.left != null) {
stack.push(curr.left);
} else if (curr.right != null) {
stack.push(curr.right);
}
// traverse up the tree from the left
} else if (curr.left == prev) {
if (curr.right != null) {
stack.push(curr.right);
}
// traverse up the tree from the right
} else {
result.add(curr.val);
stack.pop();
}
prev = curr;
}
return result;
}
Construct Binary Trees From Traversals
Lintcode Problem: Construct Binary Tree from Preorder and Inorder Traversal
Analysis: Let's consider the following preorder and ignored traversal
Inorder: D B E A F C
Preorder: A B D E C F
In Preorder sequence, the leftmost element is the root of the binary tree. If we search the root in Inorder sequence, we can divide the all elements into left subtree elements, root and right subtree elements.
Recursively follow previous steps to left and right, we can have the final binary tree:
Algorithm:
Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
Create a new tree node tNode with the data as picked element.
Find the picked element’s index in Inorder. Let the index be inIndex.
Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
Return tNode.
static int preIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// When the arrays are empty
if (inorder.length == 0)
return null;
// Construct the root
TreeNode root = new TreeNode(preorder[preIndex]);
int inIndex = find(inorder, preorder[preIndex]);
preIndex++;
// When the node is leaf
// No need to create subtrees
// Directly return the node
if (inorder.length == 1)
return root;
// Create left subtree and right subtree
if (inIndex >= 0){
int[] left = new int[inIndex];
int[] right = new int[inorder.length-inIndex-1];
newArray(inorder, left, 0);
newArray(inorder, right, inIndex+1);
root.left = buildTree(preorder, left);
root.right = buildTree(preorder, right);
}
return root;
}
// Helper method to find the index of the elements
private int find(int[] array, int item){
int size = array.length;
for (int i=0; i<size; i++){
if (array[i] == item)
return i;
}
return -1;
}
// Helper method to assign values to new arrays
private void newArray(int[] inorder, int[] new_array, int inStart){
int size = new_array.length;
for (int i=0; i<size; i++){
new_array[i] = inorder[inStart+i];
}
}
Lintcode Problem: Construct Binary Tree from Inorder and Postorder Traversal
Analysis: Very similar to the previous problem. The only difference is that we need to traverse the postorder sequence from the end to start.
One more thing need to mention: When assign children of a node, need to assign right child first cause end-to-start traversal of postorder sequence will get right child first.
Breadth-First Traversal
There is only one breadth-first traversal algorithm: Level-Order Traversal
In a level-order traversal, visit the root first, then all the depth-1 nodes
(from left to right), then all the depth-2 nodes, et cetera.
Level-Order Traversal can be easily conducted using BFS algorithm with help of queue. Java only offers Queue Interface, so need to be careful when declare a queue. Can use LinkedList or PriorityQueue class to implement, we use LinkedList as example here:
Queue<TreeNode> new_queue = LinkedList<TreeNode>();
new_queue.offer(); // Enqueue element to the tail of queue
new_queue.poll(); // Dequeue from head
new_queue.isEmpty(); // Check if empty
new_queue.peek(); // Return the head but not remove
new_queue.size(); // Return the size of the queue<>
LintCode Problem: Binary Tree Level Order Traversal
Analysis: Problem requires to perform level-order traversal. Use a queue to complete the work of separate levels. Need to use queue.size() to separate levels.
LintCode Problem: Binary Tree Level Order Traversal II
Analysis: Problem requires to return a bottom-up level-order traversal. Coordinate a queue with a stack to complete the task. In stack, separate elements of different levels by null node.
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
ArrayList output = new ArrayList();
Stack<TreeNode> stack = new Stack<TreeNode>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode temp;
int size;
if (root == null)
return output;
// Transfer nodes from queue to stack
queue.offer(root);
while(!queue.isEmpty()){
size = queue.size();
// Push elements into stack separate levels by null
for (int i=1; i<=size; i++){
temp = queue.poll();
// Be aware of the enqueue order
if (temp.right != null)
queue.offer(temp.right);
if (temp.left != null)
queue.offer(temp.left);
stack.push(temp);
}
stack.push(null);
}
ArrayList<Integer> level = new ArrayList<Integer>();
// Remove the top null
stack.pop();
while (!stack.isEmpty()){
temp = stack.pop();
// Every time encounter null, assign a new ArrayList
if (temp == null){
output.add(level);
level = new ArrayList<Integer>();
}
else{
level.add(temp.val);
}
}
// Need to add the root additionally cause no null under root
output.add(level);
return output;
}
LintCode Problem: Zigzag Level Order Traversal
Analysis: Very similar to first level-order traversal problem, only need to reverse the order of odd-level elements. Here, we use a static method of Java.util.Collections class: Collections.reverse(List), which will reverse the elements of a list.
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList output = new ArrayList();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode temp;
int size;
if (root == null)
return output;
queue.offer(root);
int level_num = 0;
while (!queue.isEmpty()){
ArrayList<Integer> level = new ArrayList<Integer>();
size = queue.size();
for (int i=1; i<=size; i++){
temp = queue.poll();
level.add(temp.val);
if (temp.left != null)
queue.offer(temp.left);
if (temp.right != null)
queue.offer(temp.right);
}
// Determine if need to reverse
if (level_num%2 != 0)
Collections.reverse(level);
output.add(level);
level_num++;
}
return output;
}