Interview Questions

Tree traversal algorithms
Tree traversal is the process of visiting each node in a tree, such as a binary tree or binary search tree, exactly once. There are several effective traversal algorithms which we will cover below. All of the algorithms below will implement Node objects we create, which were covered in a previous algorithm on linked lists. Although, we will be slightly changing the code for the nodes. The tree we will be operating on looks like the following: And we can assume the tree is properly constructed via the following code which sets up nodes and links them to their proper child nodes:
```function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}

// create nodes
var root = new Node('A');
var n1 = new Node('B');
var n2 = new Node('C');
var n3 = new Node('D');
var n4 = new Node('E');

// setup children
root.left = n1;
root.right = n2;
n1.left = n3;
n1.right = n4;
```
```class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

# create nodes
root = Node('A')
n1 = Node('B')
n2 = Node('C')
n3 = Node('D')
n4 = Node('E')

# setup children
root.left = n1
root.right = n2
n1.left = n3
n1.right = n4
```

## Pre-order

A pre-order traversal on a tree performs the following steps starting from the root:
1) Return the root node value. 2) Traverse the left subtree by recursively calling the pre-order function. 3) Traverse the right subtree by recursively calling the pre-order function.
For the tree above, performing a pre-order traversal would output the node values in the following order: A, B, D, E, C For the actual code implementation, we will be maintaining an array for the order of the nodes:
```function pre_order(root, nodes) {
nodes.push(root.data);
if (root && root.left) {
pre_order(root.left, nodes);
}
if (root && root.right) {
pre_order(root.right, nodes);
}
return nodes;
}

pre_order(root, []); // => [ A, B, D, E, C ]
```
```def pre_order(root, nodes):
nodes.append(root.data)
if root and root.left:
pre_order(root.left, nodes)
if root and root.right:
pre_order(root.right, nodes)
return nodes

print pre_order(root, []) # => ['A', 'B', 'D', 'E', 'C']
```

## In-order

An in-order traversal on a tree performs the following steps starting from the root:
1) Traverse the left subtree by recursively calling the in-order function. 2) Return the root node value. 3) Traverse the right subtree by recursively calling the in-order function.
For the tree above, performing an in-order traversal would output the node values in the following order: D, B, E, A, C
```function in_order(root, nodes) {
if (root && root.left) {
in_order(root.left, nodes);
}
nodes.push(root.data);
if (root && root.right) {
in_order(root.right, nodes);
}
return nodes;
}

in_order(root, []); // => [ D, B, E, A, C ]
```
```def in_order(root, nodes):
if root and root.left:
in_order(root.left, nodes)
nodes.append(root.data)
if root and root.right:
in_order(root.right, nodes)
return nodes

print in_order(root, []) # => ['D', 'B', 'E', 'A', 'C']
```
You can see that the only difference between the code for the in-order vs. pre-order traversal is where the appending of the node value is placed in the code. For post-order traversal below, that will be the only change as well. A good way to remember when to return the node value (or append the node value to an array) is, for pre-order do it first, for in-order do it between the left and right traversal, and as you'll see below, for post-order do it after traversing the left and right subtrees.

## Post-order

A post-order traversal on a tree performs the following steps starting from the root:
1) Traverse the left subtree by recursively calling the post-order function. 2) Traverse the right subtree by recursively calling the post-order function. 3) Return the root node value.
For the tree above, performing a post-order traversal would output the node values in the following order: D, E, B, C, A
```function post_order(root, nodes) {
if (root && root.left) {
post_order(root.left, nodes);
}
if (root && root.right) {
post_order(root.right, nodes);
}
nodes.push(root.data);
return nodes;
}

post_order(root, []); // => [ D, E, B, C, A ]
```
```def post_order(root, nodes):
if root and root.left:
post_order(root.left, nodes)
if root and root.right:
post_order(root.right, nodes)
nodes.append(root.data)
return nodes

print post_order(root, []) # => ['D', 'E', 'B', 'C', 'A']
```

## Level-order

A level-order traversal on a tree performs the following steps starting from the root:
1) Add the root to a queue. 2) Pop the last node from the queue, and return its value. 3) Add all children of popped node to queue, and continue from step 2 until queue is empty.
For the tree above, performing a level-order traversal would output the node values in the following order: A, B, C, D, E
```function level_order(root, nodes) {
var queue = [root];
while (queue.length > 0) {
// front of queue is at element 0 and we push elements to back of queue
var n = queue.shift();
nodes.push(n.data);
if (n.left !== null) { queue.push(n.left); }
if (n.right !== null) { queue.push(n.right); }
}
return nodes;
}

level_order(root, []); // => [ A, B, C, D, E ]
```
```def level_order(root, nodes):
queue = [root]
while queue:
n = queue.pop(0)
nodes.append(n.data)
if n.left:
queue.append(n.left)
if n.right:
queue.append(n.right)
return nodes

print level_order(root, []) # => ['A', 'B', 'C', 'D', 'E']
```

## Applications of tree traversals

The algorithms above have several use cases in software and development. Below is a list of some of these common cases:
1) To construct any binary tree, you need the in-order traversal array of nodes and either a pre-order or post-order array. 2) A binary search tree can be constructed using only its pre-order traversal array. 3) The in-order traversal of a binary search tree produces the elements in sorted order. 4) You can perform a breadth-first search on a tree using a level-order traversal.
mrdaniel published this on 5/31/16 |
• +
• 8
• -
• Wow, thank you for posting this. This is extremely helpful.
• +
• 2
• -
• Java Code InOrder ``` public void inOrder(Node root){ inOrder(root.left); System.out.println(root.data + " "); inOrder(root.right); } ``` PreOrder ``` public void preOrder(Node root){ System.out.println(root.data + " "); preOrder(root.left); preOrder(root.right); } ``` PostOrder ``` public void postOrder(Node root){ postOrder(root.left); postOrder(root.right); System.out.println(root.data + " "); } ```
• +
• 2
• -
• In Go: ``` package main import( "fmt" ) type Data rune func (d Data) String() string { return fmt.Sprintf("%c", rune(d)) } type Node struct { data Data left, right *Node } func (root *Node) PreOrder(nodes []Data) []Data { if root == nil { return nodes } nodes = append(nodes, root.data) if root.left != nil { nodes = root.left.PreOrder(nodes) } if root.right != nil { nodes = root.right.PreOrder(nodes) } return nodes } func (root *Node) InOrder(nodes []Data) []Data { if root == nil { return nodes } if root.left != nil { nodes = root.left.InOrder(nodes) } nodes = append(nodes, root.data) if root.right != nil { nodes = root.right.InOrder(nodes) } return nodes } func (root *Node) PostOrder(nodes []Data) []Data { if root == nil { return nodes } if root.left != nil { nodes = root.left.PostOrder(nodes) } if root.right != nil { nodes = root.right.PostOrder(nodes) } nodes = append(nodes, root.data) return nodes } func (root *Node) LevelOrder(nodes []Data) []Data { queue := []*Node{ root } for len(queue) > 0 { var n *Node // Pop n, queue = queue[0], queue[1:] nodes = append(nodes, n.data) if n.left != nil { queue = append(queue, n.left) } if n.right != nil { queue = append(queue, n.right) } } return nodes } func NewLeaf(data Data) *Node { return &Node{ data: data, } } func NewNode(data Data, left, right *Node) *Node { return &Node{ data: data, left: left, right: right, } } func main() { // create nodes n4 := NewLeaf('E') n3 := NewLeaf('D') n2 := NewLeaf('C') n1 := NewNode('B', n3, n4) root := NewNode('A', n1, n2) // empty list empty := []Data{} // do operations fmt.Println("Pre Order:", root.PreOrder(empty)) fmt.Println("In Order:", root.InOrder(empty)) fmt.Println("Post Order:", root.PostOrder(empty)) fmt.Println("Level Order:", root.LevelOrder(empty)) } ```
• +
• 1
• -
• ``` class Node: def __init__(self, data): self.data=data self.left=None self.right=None root = Node('A') n1 = Node('B') n2 = Node('C') n3 = Node('D') n4 = Node('E') root.left=n1 root.right=n2 n1.left=n3 n1.right=n4 def pre_order(root,nodes): nodes.append(root.data) if root and root.left: pre_order(root.left,nodes) if root and root.right: pre_order(root.right,nodes) return nodes print(pre_order(root,[])) def in_order(root,nodes): if root and root.left: in_order(root.left,nodes) nodes.append(root.data) if root and root.right: in_order(root.right,nodes) return nodes print(in_order(root,[])) def post_order(root,nodes): if root and root.left: post_order(root.left,nodes) if root and root.right: post_order(root.right,nodes) nodes.append(root.data) return nodes print(post_order(root,[])) def level_order(root,nodes): queue=[root] while queue: n=queue.pop(0) nodes.append(n.data) if n.left: queue.append(n.left) if n.right: queue.append(n.right) return nodes print(level_order(root,[])) ```
• +
• 1
• -
• There is something that I don't understand about the pre_order traversal algorithm. Once you get to B you call: pre_order(D, [A,B]) Which results in this array: [A,B,D] But D.left and D.right are both null, so wouldn't the if statements both fail and simply return the array [A,B,D]?
• +
• 0
• -
• In pre_order traversal algorithm what is
``` nodes.append(root.data)
```