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.

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.