Nov 8, 2018

Example of Binary Tree Preorder Traversal in Java

Preorder binary tree traversal is a classic interview problem about trees.

When doing a preorder traversal, for any node we would print the node itself, then follow the left subtree, and after that follow the right subtree. Parent node is processed before its children

First, we must have a Node class that represents each individual node in the tree.

Given the Node class above, let’s write a recursive method that will actually do the preorder traversal for us.

Because every node is “examined” once, the running time of this algorithm is O(n).

Another solution is to use stack. The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.