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

Until all nodes are traversed ? Step 1 ? Visit root node. Step 2 ? Recursively traverse left subtree. Step 3 ? Recursively traverse right subtree.

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

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList preorderTraversal(TreeNode root) { ArrayList returnList = new ArrayList(); if(root == null) return returnList; Stack stack = new Stack(); stack.push(root); while(!stack.empty()){ TreeNode n = stack.pop(); returnList.add(n.val); if(n.right != null){ stack.push(n.right); } if(n.left != null){ stack.push(n.left); } } return returnList; } }

Root 2 2 Left Subtree Right Subtree