Skip to main content

Tree (Data Structure)

Traversals​

As noted in the Wikipedia article on tree traversal (the notes below make heavy use of this article from conceptual points to pseudocode renderings):

In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g., retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.

Traversals can apply to any kind of tree (e.g., nn-ary tree), but binary trees are the ones that come up most often in interviews. Everything below concerns binary trees specifically.

Depth first search (DFS)​

The "Tick Trick"​

One online resource does a good job of detailing the so-called tick trick, a handy trick for figuring out by hand the order in which a binary tree's nodes will be "visited" for the pre-order, in-order, and post-order traversals:

  1. Draw an arrow as a path around the nodes of the binary tree diagram, closely following its outline. The direction of the arrow depends on whether you are traversing the tree left-to-right or right-to-left.
  2. Draw a line or tick mark on one of the sides or the bottom of each node in the tree. Where you draw the mark depends on which traversal you are attempting to perform, as shown in the diagram below:

The point at which the path you've drawn around the binary tree intersects the tick mark is the point at which that node will be "visited" during the traversal. Examples for pre-, post-, and in-order traversals are provided below (left-to-right and right-to-left).

Correspondence between Left-to-Right and Right-to-Left Traversals

It may be tempting to think that right-to-left traversals should effectively be "reversals" of their left-to-right counterparts, but this is not the case for pre- and post-order traversals. It is only the case for in-order traversals.

To see why, recall what the various traversals actually mean. A pre-order traversal means we will visit the current node before traversing either of its subtrees whereas a post-order traversal means we will visit the current node after traversing both of its subtrees. In either case, the root node itself serves as a point of clarification:

        __A______          | Pre-order  (L -> R): A B X E M S W T P N C H
       /         \         | Pre-order  (R -> L): A W C H T N P B S X M E
    __B         __W__      | Post-order (L -> R): E M X S B P N T H C W A
   /   \       /     \     | Post-order (R -> L): H C N P T W S M E X B A
  X     S     T       C    | In-order   (L -> R): E X M B S A P T N W H C
 / \         / \     /     | In-order   (R -> L): C H W N T P A S B M X E
E   M       P   N   H      |

How could the left-to-right and right-to-left pre-order traversals be reversals of each other if they both start with the same node? Similarly, the post-order traversals cannot be reversals of each other if they both end with the same node. But what about in-order traversals? As can be seen above, the order in which the nodes are visited is reversed when we change the traversal from left-to-right to right-to-left.

It is worth noting that the left-to-right pre-order traversal is effectively the reverse of the right-to-left post-order traversal. Similarly, the left-to-right post-order traversal is effectively the reverse of the right-to-left pre-order traversal.

Use the binarytree Package for Python

Learning about trees can become overly cumbersome if you are specifying all of the nodes yourself. For example, the binary tree in the tip above (and the one we will see throughout the subsections below) may be set up in Python without any package support as follows:

See the setup
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
n1 = TreeNode('A')
n2 = TreeNode('B')
n3 = TreeNode('W')
n4 = TreeNode('X')
n5 = TreeNode('S')
n6 = TreeNode('T')
n7 = TreeNode('C')
n8 = TreeNode('E')
n9 = TreeNode('M')
n10 = TreeNode('P')
n11 = TreeNode('N')
n12 = TreeNode('H')

n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n4.left = n8
n4.right = n9
n3.left = n6
n3.right = n7
n6.left = n10
n6.right = n11
n7.left = n12

That's not fun. The binarytree package makes things much easier to work with. The same tree can be set up as follows:

from binarytree import build2
bin_tree = build2(['A', 'B', 'W', 'X', 'S', 'T', 'C', 'E', 'M', None, None, 'P', 'N', 'H'])

The code in the sections below will rely on binarytree for the sake of simplicity.

Pre-order​

In a pre-order traversal of a binary tree, we "visit" a node and then traverse both of its subtrees. Usually, we traverse the node's left subtree first and then traverse the node's right subtree. Below is an example (using the tick trick) of a left-to-right preorder traversal of a binary tree:

We get the following output by printing the value of each node as we "visit" it:

A B X E M S W T P N C H

Alternatively, we can perform a preorder traversal from right-to-left instead of left-to-right. This is done by traversing the node's right subtree before we traverse its left subtree:

We get the following output by printing the value of each node as we "visit" it:

A W C H T N P B S X M E

Recursive​

Pseudocode for recursive pre-order DFS
procedure preorder(node)
    if node = null
        return
    visit(node)
    preorder(node.left)
    preorder(node.right)

Iterative​

Pseudocode for iterative pre-order DFS
procedure iterativePreorder(node)
    if node = null
        return
    stack ← empty stack
    stack.push(node)
    while not stack.isEmpty()
        node ← stack.pop()
        visit(node)
        // right child is pushed first so that left is processed first
        if node.right ≠ null
            stack.push(node.right)
        if node.left ≠ null
            stack.push(node.left)

Post-order​

In a postorder traversal of a binary tree, we traverse both subtrees of a node, and then we "visit" the node. Usually we traverse the node's left subtree first and then traverse the node's right subtree:

We get the following output by printing the value of each node as we "visit" it:

E M X S B P N T H C W A

Alternatively, we can perform a post-order traversal from right-to-left instead of left-to-right. This is done by traversing the node's right subtree before we traverse its left subtree:

We get the following output by printing the value of each node as we "visit" it:

H C N P T W S M E X B A

Recursive​

Pseudocode for recursive post-order DFS
procedure postorder(node)
    if node = null
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Iterative​

Pseudocode for iterative post-order DFS
procedure iterativePostorder(node)
    stack ← empty stack
    lastNodeVisited ← null
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            peekNode ← stack.peek()
            // if right child exists and traversing node
            // from left child, then move right
            if peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right
                node ← peekNode.right
            else
                visit(peekNode)
                lastNodeVisited ← stack.pop()

In-order​

In an in-order traversal of a binary tree, we traverse one subtree of a node, then "visit" the node, and then we traverse its other subtree. Usually, we traverse the node's left subtree first and then traverse the node's right subtree:

We get the following output by printing the value of each node as we "visit" it:

E X M B S A P T N W H C

Alternatively, we can perform an in-order traversal from right-to-left instead of left-to-right. This is done by traversing the node's right subtree before we traverse its left subtree:

C H W N T P A S B M X E

Recursive​

Pseudocode for recursive in-order DFS
procedure inorder(node)
    if node = null
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

Iterative​

Pseudocode for iterative in-order DFS
procedure iterativeInorder(node)
    stack ← empty stack
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            node ← stack.pop()
            visit(node)
            node ← node.right

Breadth first search (BFS)​

Level order traversal​

In a level order traversal of a binary tree, we traverse all of the tree nodes on level 0, then all of the nodes on level 1, etc. The "tick trick" does not work for this traversal, but there's no real need for it, since the order the nodes will be traversed is easy to determine by hand.

Below is an example of a left-to-right level-order traversal of a binary tree:

We get the following output by printing the value of each node as we "visit" it:

A B W X S T C E M P N H

Alternatively, we can perform a level order traversal from right-to-left instead of left-to-right:

We get the following output by printing the value of each node as we "visit" it:

A W B C T S X H N P M E
Without isolated levels
procedure levelorder(node)
    queue ← empty queue
    queue.enqueue(node)
    while not queue.isEmpty()
        node ← queue.dequeue()
        visit(node)
        if node.left ≠ null
            queue.enqueue(node.left)
        if node.right ≠ null
            queue.enqueue(node.right)

The pseudocode above (from Wikipedia) is the standard BFS implementation for a binary tree traversal, where we only care about visiting all nodes, level by level, left to right. But it's fairly common to encounter algorithm problems that demand you do something (i.e., perform some logic) on a level by level basis; that is, you effectively need to isolate the nodes by level. The pseudocode above does not do this, but we can easily fix this ourselves:

Isolated levels
procedure levelorder(node)
    queue ← empty queue
    queue.enqueue(node)
    while not queue.isEmpty()
        // retrieve number of nodes on current level
        numNodesThisLevel ← queue.length

        // perform logic for current level
        for each node in level do
          node ← queue.dequeue()

          // perform logic on current node
          visit(node)

          // enqueue nodes on next level (left to right)
          if node.left ≠ null
              queue.enqueue(node.left)
          if node.right ≠ null
              queue.enqueue(node.right)

The Python code snippets in the other tabs reflect this approach since it is the most likely approach needed in the context of solving interview problems.