Practice depth first traversals

Interviewers love to ask questions that include depth first traversals in some shape or form, these questions are much easier to solve when you have a good example of a tree and you’ve fully internalized the route of the traversals.

This post includes a quick introduction to the most common depth first traversals (in-order, pre-order and post-order) and a practice.

In-order traversal:  L-N-R (Left, Current Node, Right)

in-order traversal starts from the left most node, move to the current node, and to the rights node.

Given the tree below, in-order traversal will visit the nodes in an alphabetical order. A, B, C, D, E, F, G, H, I.

image

Here’s the recursive implementation

private static void getInorderRecursive(
BinaryTreeNode<Character> node,
List<BinaryTreeNode<Character>> result) {

if (node == null) {
return;
}
// Go left all the way
getInorderRecursive(node.getLeft(), result);
// Visit current node
result.add(node);
// Go right all the way
getInorderRecursive(node.getRight(), result);
}

Here’s the iterative implementation

public static List<BinaryTreeNode<Character>> getInorderIterative(BinaryTreeNode<Character> node) {
List<BinaryTreeNode<Character>> result = new ArrayList<>();

Stack<BinaryTreeNode<Character>> stack = new Stack<>();

while (!stack.isEmpty() || node != null) {
if (node != null) {
// as long as the node to the left is not null:
// add it to the stack and moved to the next left node...
stack.push(node);
node = node.getLeft();
} else {
// When no more nodes to the left:
// visit the last node found at the left
node = stack.pop();
result.add(node);

// Continue with the right node of the last node found at the left.
// We will be adding it's left nodes to the stack.
node = node.getRight();
}
}

return result;
}

Post-order traversal:  L-R-N (Left, Right, Current Node)

Post-order traversal starts from the left most node, move to the right node, and to the current node.

Given the tree below, Post-order traversal will visit the nodes in the following order: A, C, E, D, B, H, I, G, F.

image

Here’s the recursive implementation

private static void getPostorderRecursive(
BinaryTreeNode<Character> node,
List<BinaryTreeNode<Character>> result) {

if (node == null) {
return;
}
// Go left all the way
getPostorderRecursive(node.getLeft(), result);
// Go right all the way
getPostorderRecursive(node.getRight(), result);
// Visit current node
result.add(node);
}

Pre-order traversal:  N-L-R (Current Node, Left, Right)

Pre-order traversal starts from the current node, move to the left node, and to the right node.

Given the tree below, Pre-order traversal will visit the nodes in the following order: F, B, A, D, C, E, G, I, H.

Here’s the recursive implementation

private static void getPreorderRecursive(
BinaryTreeNode<Character> node,
List<BinaryTreeNode<Character>> result) {

if (node == null) {
return;
}
// Visit current node
result.add(node);
// Go left all the way
getPreorderRecursive(node.getLeft(), result);
// Go right all the way
getPreorderRecursive(node.getRight(), result);
}

Practice (In-order)

Here’s a good practice to help you internalize the route of the traversals

Given any node in the tree, write a function that find the next node of in order traversal, provided that all nodes include a link to their parent.

Approach

Lets look at the in order route again (Left, Current Node, Right). Notice that in-order traversal visit the nodes in their alphabetical order: A, B, C, D, E, F, G, H, I. So for example, if the given node is A, the next node would be B. If the given node it C, the next node would be … D, and so on.

image

Since we need to reverse engineer the in order traversal recursion, before we design the solution it’s best to write down the recursive stack (starting from the root) :

private static void getInorderRecursive(
BinaryTreeNode<Character> node,
List<BinaryTreeNode<Character>> result) {

if (node == null) {
return;
}
// Go left all the way
getInorderRecursive(node.getLeft(), result);
// Visit current node
result.add(node);
// Go right all the way
getInorderRecursive(node.getRight(), result);
}

Stack:

  1. getInorderRecursive (F)
    1. (go left) getInorderRecursive (B)
      1. (go left) getInorderRecursive (A)
        1. Nothing to the left
        2. Visit (A)
        3. Nothing to the right
      2. Visit (B)
      3. (go right) getInorderRecursive (D)
        1. (go left) getInorderRecursive (C)
          1. Nothing to the left
          2. Visit (C)
          3. Nothing to the right
        2. Visit (D)
        3. (go right) getInorderRecursive (E)
          1. Nothing to the left
          2. Visit (E)
          3. Nothing to the right
    2. Visit (F)
    3. (go right) getInorderRecursive (G)
      1. Nothing to the left
      2. Visit (G)
      3. (go right) getInorderRecursive (I)
        1. (go left) getInorderRecursive (H)
          1. Nothing to the left
          2. Visit (H)
          3. Nothing to the right
        2. Visit (I)
        3. Nothing to the right

Here’s the design for finding the next node of in order traversal:

When the node has a right child (F, G, B, D), the next node would be the right child’s left most child, if exist (G, B). If right child doesn’t have left nodes (F, D), the next node would be the right child itself.

     How did I know? I saw it in the stack. After we visit a node (look at node B), the next thing that we do is call the recursion with the node’s right child (node D), the recursion calls itself again and again passing the left node (node C) until there’s no left node, at that point it returns the last node (C).

Otherwise (A, C, E, I, H), we need to climb up and get the first node that is located left to its parent. If found (A, C, E, H), return the node parent. Otherwise (I), this is the last element, return null

Tests

public class TreeDepthFirstTraversalsTest {
@Test
public void findNextNode_nodeHasRightChild() throws Exception {
// Find the next inorder node
final BinaryTreeNode<Character> root = createBinaryTreeNode();

assertNextNode(root, 'F', 'G');
assertNextNode(root, 'G', 'H');
assertNextNode(root, 'B', 'C');
assertNextNode(root, 'D', 'E');
}

@Test
public void findNextNode_nodeDoesNotHaveRightChild() throws Exception {
// Find the next inorder node
final BinaryTreeNode<Character> root = createBinaryTreeNode();

assertNextNode(root, 'A', 'B');
assertNextNode(root, 'C', 'D');
assertNextNode(root, 'E', 'F');
assertNextNode(root, 'H', 'I');
}

@Test
public void findNextNode_lastNode() throws Exception {
// Find the next inorder node
final BinaryTreeNode<Character> root = createBinaryTreeNode();
final BinaryTreeNode node = root.getNode('I');
BinaryTreeNode nextNode = TreeDepthFirstTraversals.findNextNode(node);
assertNull(nextNode);
}

private void assertNextNode(BinaryTreeNode<Character> root, char nodeData, char expectedNextNodeData) {
final BinaryTreeNode node = root.getNode(nodeData);
BinaryTreeNode nextNode = TreeDepthFirstTraversals.findNextNode(node);
assertEquals(expectedNextNodeData, nextNode.getData());

}

private BinaryTreeNode createBinaryTreeNode() {
// Add root
final BinaryTreeNode root = new BinaryTreeNode('F');
final BinaryTreeNode b = new BinaryTreeNode('B', root);
root.setLeft(b);
final BinaryTreeNode g = new BinaryTreeNode('G', root);
root.setRight(g);

// Add to B
final BinaryTreeNode a = new BinaryTreeNode('A', b);
b.setLeft(a);
final BinaryTreeNode d = new BinaryTreeNode('D', b);
b.setRight(d);

// Add to D
final BinaryTreeNode c = new BinaryTreeNode('C', d);
d.setLeft(c);
final BinaryTreeNode e = new BinaryTreeNode('E', d);
d.setRight(e);

// Add to G
final BinaryTreeNode i = new BinaryTreeNode('I', g);
g.setRight(i);
// Add to I
i.setLeft(new BinaryTreeNode('H', i));

return root;
}
}

Solution

public class TreeDepthFirstTraversals {

public static BinaryTreeNode findNextNode(BinaryTreeNode node) {
final BinaryTreeNode rightChild = node.getRight();
boolean hasRightChild = rightChild != null;
if (hasRightChild) {
return getLeftMostLookDown(rightChild);
} else {
return getAncestorLocatedLeft(node);
}
}

private static BinaryTreeNode getAncestorLocatedLeft(BinaryTreeNode node) {

BinaryTreeNode child = node;
BinaryTreeNode parent = node.getParent();
while (parent != null && parent.getLeft() != child) {
child = parent;
parent = parent.getParent();
}
return parent;
}

private static BinaryTreeNode getLeftMostLookDown(BinaryTreeNode node) {
BinaryTreeNode result = node;

while (result.getLeft() != null) {
result = result.getLeft();
}
return result;
}
}

Practice (Pre-order)

Can you do the same practice for pre-order traversal? 

Pre-order (Current, Left, Right) traversal visits the nodes in the following order: F, B, A, D, C, E, G, I, H.

private static void getPreorderRecursive(
BinaryTreeNode<Character> node,
List<BinaryTreeNode<Character>> result) {

if (node == null) {
return;
}
// Visit current node
result.add(node);
// Go left all the way
getPreorderRecursive(node.getLeft(), result);
// Go right all the way
getPreorderRecursive(node.getRight(), result);
}

Here’s the design for finding the next node of in order traversal:

When the node has a left child (F –> B, B –> A, D –> C, I –> H) - the next node would be the left child itself. We can see that clearly by looking at the recursion code. After it visit a node, it calls itself with the node’s left child, and the first thing that the recursion does is visit the node.

Otherwise (A, C, E, G, H), if the node has a right child (G –> I) - the next node would be the right child itself.

Otherwise, since the node doesn’t have a left child nor right child (A, C, E, H),  a we need to climb up and find the first node that is located to the left of it’s parent and the parent has a right child, if such node exist (A –> D, C –> E, E –> G), the result would be the node’s parent right child.

Otherwise (H), this is the last node, return null.

Solution

public static BinaryTreeNode findNextPreOrderNode(BinaryTreeNode node) {
final BinaryTreeNode leftChild = node.getLeft();
boolean hasLeftChild = leftChild != null;
if (hasLeftChild) {
return leftChild;
} else {
final BinaryTreeNode rightChild = node.getRight();
boolean hasRightChild = rightChild != null;
if (hasRightChild) {
return rightChild;
} else {
return getRightChildOfLeftyNode(node);
}
}
}

private static BinaryTreeNode getRightChildOfLeftyNode(BinaryTreeNode node) {
while (node != null){
BinaryTreeNode parent = node.getParent();
if (parent.getLeft() == node){
return parent.getRight();
}
node = parent;
}
return null;
}

Comments