Binary Tree Preorder Traversal (Java) Analysis Preorder binary tree traversal is
ID: 3909695 • Letter: B
Question
Binary Tree Preorder Traversal (Java)
Analysis
Preorder binary tree traversal is a classic interview problem about trees. The key to solve this problem is to understand the following:
What is preorder? (parent node is processed before its children)
Use Stack from Java Core library
The key is using a stack to store left and right children and push right child first so that it is processed after the left child.
In the pre-order traversal method, the root node is visited first, then the left subtree and finally the right subtree.
We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be ?
A ? B ? D ? E ? C ? F ? G
Algorithm
Please include as many comments as possible on the Java solution shown below. I think I get the pre-order traversal algorithm and the concept behind the pre-order traversal as well as most of the Java source code shown below.
Java Solution
Root 2 2 Left Subtree Right SubtreeExplanation / Answer
public class TreeNode { // That's a tree node of the tree with data as val and two children left and right
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; } // Constructor for tree node
}
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> returnList = new ArrayList<Integer>(); // This is the structure which holds the pre-order traversal sequence
if(root == null)
return returnList;
Stack<TreeNode> stack = new Stack<TreeNode>(); // Stack is created to store the tree nodes which have to be processed
stack.push(root); // root is pushed on the stack as its left and right child need to be processed
while(!stack.empty()){ // This loop is making sure that all the nodes have been processed completely
TreeNode n = stack.pop(); // poping out a node to process
returnList.add(n.val); // pushing the value of node into the arraylist
if(n.right != null){
stack.push(n.right); // right child is to be processed so it is pushed onto the stack before the left child as
} // per preorder traversal
if(n.left != null){
stack.push(n.left); // Now left child is pushed.
}
}
return returnList; // Returning the arraylist object having the pre-order traversal sequence.
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.