6.4 Binary Tree Traversals
To process trees, we need a mechanism to traverse them and that forms the topic of this section. The process of accessing all the nodes of a tree is called traversing the tree. Each node is processed only once but it can be accessed more than once. As we have seen in linear data structures (like linked lists, stacks, queues, etc.), the elements are accessed in sequential order.
But, in tree structure there are different ways. Tree traversal is like tree searching, except that in traversing the tree, the goal is to move through the tree in a particular order. In addition, all nodes are processed during browsing but the search will stop when the required node is found.
Traversal Possibilities (Ability to browse trees)
Starting at the root of the binary tree, there are three main steps that can be taken, and the order in which they are performed determines the type of traversal. The following steps are: perform an action on the current node (called “visiting” node and denoted by “D”), pass through the left child node (denoted by “L”) ) and passes through the right child node (denoted “R”). This process can be easily described through recursion. Based on the above definition, there are 6 possibilities:
- LDR: Process the left subtree, process the current node data, and then process the right subtree.
- LRD: Process the left subtree, process the right subtree and then process the current node data.
- DLR: Process the current node data, process the left subtree, and then process the right subtree.
- DRL: Process the current node data, process the right subtree and then process the left subtree.
- RDL: Process the right subtree, process the current node data, and then process the left subtree.
- RLD: Process the right subtree, process the left subtree, and then process the current node data.
Classifying the Traversals
The sequence in which nodes are processed determines a particular browsing method. The classification is based on the order in which the current node is processed. That is to say, if we are sorting based on the current node (D) and if D is in the middle, it doesn’t matter whether L is to the left of D or R is to the left of D. Similarly, it doesn’t matter whether L is to the right of D or R is to the right of D. Thus, the total of 6 possibilities is reduced to 3 and that is:
- Preorder (DLR) Traversal
- Inorder (LDR) Traversal
- Postorder (LRD) Traversal
There is another browsing method that does not depend on the above orders and that is:
- Level Order Traversal: This method is inspired by Breadth First Traversal (BFS of Graph algorithms).
We will use the diagram below for the rest of our discussion.
PreOrder Tradersal
In PreOrder Traversal, each node is preprocessed (before) one of its subtrees. This is the simplest interpretation. However, even though each node is pre-processed into the subtrees, it still requires some information to be maintained while moving down the tree. In the above example, 1 is processed first, then the left subtree, and then the right subtree.
Therefore, processing must return to the right subtree after finishing processing the left subtree. To switch to the right subtree after processing the left subtree, we must maintain the original information. The obvious ADT for such information is a stack. Due to its LIFO structure, it is possible to retrieve information about the right subtrees in reverse order.
Preorder traversal is defined as follows:
- Visit the original.
- Move through the left subtree in PreOrder.
- Move through the right subtree in PreOrder.
The tree nodes will be visited in the following order: 1 2 4 5 3 6 7
1 2 3 4 5 6 7 8 | public void PreOrder(BinaryTreeNode root){ if(root != null){ System.out.println(root.data); PreOrder(root.left); PreOrder(root.right); } } |
Time Complexity: O(n). Space Complexity: O(n).
Iterative Preorder Traversal
In the loop version, a stack is required because we need to remember the current node so that after completing the left subtree we can move to the right subtree. To simulate the same, we first process the current node and before moving to the left subtree, we store the current node on the stack. After finishing processing the left subtree, pop the element and move to its right subtree. Continue this process until the stack is empty.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public ArrayList<Integer> preorderTraversal(BinaryTreeNode root){ ArrayList<Integer> res = new ArrayList<>(); if(root == null) { return res; } Stack<BinaryTreeNode> s = new Stack<>(); s.push(root); while(!s.isEmpty()) { BinaryTreeNode tmp = s.pop(); res.add(tmp.data); // pay more attention to this sequence if(tmp.right != null) { s.push(tmp.right); } if(tmp.left != null) { s.push(tmp.left); } } return res; } |
InOrder Tradersal
In Inorder Traversal, the root is accessed between subtrees. Inorder browsing is defined as follows:
- Move through the left subtree in the Inorder.
- Visit the original.
- Move the subtree to the right in the Inorder.
The tree nodes will be visited in the following order: 4 2 5 1 6 3 7
1 2 3 4 5 6 7 8 | public void InOrer(BinaryTreeNode root){ if(root != null){ InOrer(root.left); System.out.println(root.data); PreOrder(root.right); } } |
Time Complexity: O(n). Space Complexity: O(n).
Non-Recursive Inorder Traversal
The non-recursive version of Inorder browse is similar to Preorder. The only change is, instead of processing the node before going to the left subtree, process it after it pops up (indicated after finishing processing the left subtree).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public ArrayList<Integer> inorderTraversal(BinaryTreeNode root){ ArrayList<Integer> res = new ArrayList<>(); Stack<BinaryTreeNode> s = new Stack<>(); BinaryTreeNode currentNode = root; boolean done = false; while(!done) { if(currentNode != null) { s.push(currentNode); currentNode = currentNode.left; } else { if(s.isEmpty()) { done = true; } else { currentNode = s.pop(); } res.add(currentNode.getData()); currentNode = currentNode.right; } } return res; } |
Time Complexity: O(n). Space Complexity: O(n).
PostOrder Tradersal
In PostOrder traversal, the root is accessed after both subtrees. The following order transmission is defined as follows:
- Move through the left subtree in the Inorder.
- Move the subtree to the right in the Inorder.
- Visit the original.
The tree nodes will be visited in the following order: 4 5 2 6 7 3 1
1 2 3 4 5 6 7 8 | public void PostOrder(BinaryTreeNode root){ if(root != null){ InOrer(root.left); PreOrder(root.right); System.out.println(root.data); } } |
Time Complexity: O(n). Space Complexity: O(n).
Non-Recursive Postorder Traversal
In preorder and inorder traversal, after placing the stack element, we don’t need to visit the same vertex again. But in postorder traversal, each node is visited twice. That means, after processing the left subtree we will access the current node and after processing the right subtree we will access the same current node. But we should handle the button in the second hit. Here the problem is how to distinguish whether we are returning from the left subtree or the right subtree.
We use a previous variable to keep track of the previously browsed node. Assume the current node is on top of the stack. When previous is the parent node of the current node, we are descending through the tree. In this case, we try to move to the left child of the current if there is one (i.e. push the left child to the stack). If it is not available, we consider the right node to match the current node. If both the left child and the right child do not exist (i.e. the current node is a leaf node), we print the value of the current node and pop it off the stack.
If previous is the left child node of the current node, we will traverse the tree from the left. We consider the right child node of the current node. If it is available, move down the right child node (ie, push the right child onto the stack); if not, print the current value and pop it off the stack. If previous is the right child node of the current, we will traverse the tree from the right. In this case, we print the current value and pop it off the stack.
The above paragraph I translated, but the feeling is still a bit entangled, there may be places where the meaning is not clear, you can refer to the author’s verbatim.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public ArrayList<Integer> postorderTraversal(BinaryTreeNode root){ ArrayList<Integer> res = new ArrayList<>(); if(root == null) { return res; } Stack<BinaryTreeNode> s = new Stack<>(); s.push(root); BinaryTreeNode prev = null; while(!s.isEmpty()) { BinaryTreeNode curr = s.peek(); if(prev == null || prev.left == curr || prev.right == curr) { // traverse from top to bottom, and if curr has left child or right child, // push into the stack; otherwise, pop out. if(curr.left != null) { s.push(curr.left); } else if(curr.left == prev) { if(curr.right != null) { s.push(curr.right); } } } else if(curr.left == prev) { if(curr.right != null) { s.push(curr.right); } } else { res.add(curr.data); s.pop(); } prev = curr; } return res; } |
Time Complexity: O(n). Space Complexity: O(n).
Level Order Traversal
Level Order Traversal is defined as follows:
- Visit the original.
- While going through level 1, keep all elements at level 1 in the queue.
- Go to the next level and access all the buttons in that level.
- Repeat this until all levels are completed.
The tree nodes are visited in the following order: 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public ArrayList<ArrayList<Integer>> levelOrder(BinaryTreeNode root){ ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if(root == null) { return res; } //Initialization Queue<BinaryTreeNode> q = new LinkedList<>(); q.offer(root); q.offer(null); ArrayList<Integer> curr = new ArrayList<>(); while(!q.isEmpty()) { BinaryTreeNode tmp = q.poll(); if(tmp != null) { curr.add(tmp.data); if(tmp.left != null) { q.offer(tmp.left); } if(tmp.right != null) { q.offer(tmp.right); } } else { ArrayList<Integer> c_curr = new ArrayList<>(curr); res.add(c_curr); curr.clear(); // Java will clear the reference, so have to new an new ArrayList, complition of a level if(!q.isEmpty()) { q.offer(null); } } } return res; } |
Time Complexity: O(n). Space Complexity: O(n). Because in the worst case, all the nodes on the entire last level can be in the queue simultaneously.