Binary Tree Traversal

Posted on | Post modified | In , , , , ,

Binary Tree Traversals (Inorder, Preorder and Postorder)

An example binary tree

The inorder enumeration for the tree above is B D A G E C H F I

The preorder enumeration for the tree above is A B D C E G F H I

The postorder enumeration for the tree above is D B G E H I F C A

How to solve different types of tree traversal problem via Prolog?

In prolog, the example tree can be described as follows:

1
2
3
4
5
6
7
8
9
node(a, b, c).
node(b, nil, d).
node(c, e, f).
node(e, g, nil).
node(f, h, i).
leaf(d).
leaf(g).
leaf(h).
leaf(i).

Inorder

recursive relationship:

node a => b d a g e c h f i => (b d) a (g e c h f i) => left child traversal result + node + right child traversal result

node b (node a’s left child) => b d

node c (node a’s right child) => g e c h f i

1
2
3
4
5
6
7
8
9
10
11
12
13
% base case
inorder(Node, [Node]) :-
    leaf(Node).
inorder(nil, []).

inorder(Node, TraversalResult) :-
    node(Node, LeftChild, RightChild),
    inorder(LeftChild, TraversalFromLC),
    inorder(RightChild, TraversalFromRC),
    append(TraversalFromLC, [Root| TraversalFromRC], TraversalResult).

?- inorder(A, Res).
Res = [b, d, a, g, e, c, h, f, i]

or

1
2
3
4
5
6
7
8
9
10
11
inorder1(Node, List, Tail) :-
  node(Node, Child1, Child2),
  inorder1(Child1, List, Tail1),
  Tail1 = [Node|List1],
  inorder1(Child2, List1, Tail).
inorder1(Node, [Node|Tail], Tail) :-
  leaf(Node).
inorder1(nil, Tail, Tail).

inorder(Node, List) :-
  inorder1(Node, List, []).

Which inorder traversal algorithm has better time complexity?

Preorder

recursive relationship:

node a => a b d c e g f h i=> a (b d) (c e g f h i) => node + left child traversal result + right child traversal result

node b (node a’s left child) => b d

node c (node a’s right child) => c e g f h i

1
2
3
4
5
6
7
8
9
10
11
12
13
% base case
preorder(Node, [Node]) :-
    leaf(Node).
preorder(nil, []).

preorder(Node, TraversalResult) :-
    node(Node, LeftChild, RightChild),
    preorder(LeftChild, TraversalFromLC),
    preorder(RightChild, TraversalFromRC),
    append([Root|TraversalFromLC], TraversalFromRC, TraversalResult).

?- preorder(a, Res).
Res = [a, b, d, c, e, g, f, h, i]

or

1
2
3
4
5
6
7
8
9
10
11
preorder1(Node, List, Tail) :-
  node(Node, Child1, Child2),
  List = [Node|List1],
  preorder1(Child1, List1, Tail1),
  preorder1(Child2, Tail1, Tail).
preorder1(Node, [Node|Tail], Tail) :-
  leaf(Node).
preorder1(nil, Tail, Tail).

preorder(Node, List) :-
  preorder1(Node, List, []).

Which preorder traversal algorithm has better time complexity?

Postorder

recursive relationship:

node a => d b g e h i f c a=> (d b) (g e h i f c) a => left child traversal result + right child traversal result + node

node b (node a’s left child) => d b

node c (node a’s right child) => g e h i f c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
% base case
postorder(Node, [Node]) :-
    leaf(Node).
postorder(nil, []).

postorder(Node, TraversalResult) :-
    node(Node, LeftChild, RightChild),
    postorder(LeftChild, TraversalFromLC),
    postorder(RightChild, TraversalFromRC),
    append(TraversalFromLC, TraversalFromRC, Temp),
    append(Temp, [Node], TraversalResult).

?- postorder(a, Res).
Res = [d, b, g, e, h, i, f, c, a]

or

1
2
3
4
5
6
7
8
9
10
11
postorder1(Node, List, Tail) :-
  node(Node, Child1, Child2),
  postorder1(Child1, List, Tail1),
  postorder1(Child2, Tail1, Tail2),
  Tail2=[Node|Tail].
postorder1(Node, [Node|Tail], Tail) :-
  leaf(Node).
postorder1(nil, Tail, Tail).

postorder(Node, List) :-
  postorder1(Node, List, []).

Which postorder traversal algorithm has better time complexity?

How to solve different types of tree traversal problem via Python?

In python, the example tree can be described as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Root = TreeNode('A')
Root.left = TreeNode('B')
Root.right = TreeNode('C')
Root.left.right = TreeNode('D')
Root.right.left = TreeNode('E')
Root.right.left.left = TreeNode('G')
Root.right.right = TreeNode('F')
Root.right.right.left = TreeNode('H')
Root.right.right.right = TreeNode('I')

Inorder (Recursive)

1
2
3
4
5
6
7
8
9
10
def inorderTraversal(self, root):
    if not root:
        return []

    ret = []
    ret.extend(inorderTraversal(root.left))
    ret.extend([root.val])
    ret.extend(inorderTraversal(root.right))

    return ret

or

1
2
3
4
5
6
7
8
9
10
11
def inorderTraversal(root):
    def helper(root, res):
        if root:
            helper(root.left, res)
            res.append(root.val)
            helper(root.right, res)

	res = []
    helper(root, res)

    return res

Inorder (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def inorderTraversal(root):
    stack = [(root, False)]
    ret = []

    while stack:
        node, visited = stack.pop()
        if node:
            if not visited:
                stack.append((node.right, False))
                stack.append((node, True))
                stack.append((node.left, False))
            else:
                ret.append(node.val)

    return ret

Preorder (Recursive)

1
2
3
4
5
6
7
8
9
def preorderTraversal(root):
    if not root:
        return []

    ret = [root.val]
    ret.extend(preorderTraversal(root.left))
    ret.extend(preorderTraversal(root.right))

    return ret

or

1
2
3
4
5
6
7
8
9
10
11
12
def preorderTraversal(root, ret = []):
    if not root:
        return []
    
    if not ret:
        ret = []
        
    ret.append(root.val)
    preorderTraversal(root.left, ret)
    preorderTraversal(root.right, ret)

    return ret

Preorder (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
def preorderTraversal(root):
    dq = collections.deque([root])
    ret = []

    while dq:
        node = dq.popleft()

        if node:
            ret.append(node.val)
            dq.appendleft(node.right)
            dq.appendleft(node.left)

        return ret

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preorderTraversal(root):
    if not root:
        return []

    ret = []
    stack = [root]

    while stack:
        node = stack.pop()
        if node:
            ret.append(node.val)
            stack.append(node.right)
            stack.append(node.left)

    return ret

Postorder (Recursive)

1
2
3
4
5
6
7
8
9
10
def postorderTraversal(root):
    if not root:
        return []

    ret = []
    ret.extend(postorderTraversal(root.left))
    ret.extend(postorderTraversal(root.right))
    ret.append(root.val)

    return ret

or

1
2
3
4
5
6
7
8
9
10
11
def postorderTraversal(root):
    def helper(root, nodes):
        if not root:
            return
        helper(root.left, nodes)
        helper(root.right, nodes)
        nodes.append(root.val)

    ret = []
    helper(root, ret)
    return ret

Postorder (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def postorderTraversal(root):
    stack = [(root, False)]
    ret = []

    while stack:
        node , visited = stack.pop()
        if node:
            if not visited:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
            else:
                ret.append(node.val)

    return ret

Reference

https://www.ida.liu.se/opendsa/OpenDSA/Books/TDDD86_2014/html/BinaryTreeTraversal.html