Binary tree traversal - inorder, preorder and postorder

Posted on Edited on In , Views:

Tree node definition

1
2
3
4
5
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

To build the tree nodes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
root = Node(0)
n1 = Node(1)
n2 = Node(2)
root.left = n1
root.right = n2
n3 = Node(3)
n4 = Node(4)
n1.left = n3
n1.right = n4
n5 = Node(5)
n6 = Node(6)
n2.left = n5
n2.right = n6
n7 = Node(7)
n8 = Node(8)
n3.left = n7
n3.right = n8

The tree looks like below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
               0
             /   \
            1     2
           / \   / \
          3   4 5   6
         / \
        7   8 

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
```  
   
To build the tree nodes:

```python
root = Node(0)
n1 = Node(1)
n2 = Node(2)
root.left = n1
root.right = n2
n3 = Node(3)
n4 = Node(4)
n1.left = n3
n1.right = n4
n5 = Node(5)
n6 = Node(6)
n2.left = n5
n2.right = n6
n7 = Node(7)
n8 = Node(8)
n3.left = n7
n3.right = n8

The tree looks like below:

1
2
3
4
5
6
7
       0
     /   \
    1     2
   / \   / \
  3   4 5   6
 / \
7   8

Pre-order traversal

1
2
3
4
5
6
7
8
9
10
11
12
def pre_order_traverse(node):
    if node == None:
        return

    print(f"{node.val} ", end="")
    pre_order_traverse(node.left)
    pre_order_traverse(node.right)
    
pre_order_traverse(root)
print()

#Output: 0 1 3 7 8 4 2 5 6

In-order traversal

1
2
3
4
5
6
7
8
9
10
11
12
def in_order_traverse(node):
    if node == None:
        return

    in_order_traverse(node.left)
    print(f"{node.val} ", end="")
    in_order_traverse(node.right)

in_order_traverse(root)
print()
    
#Output: 7 3 8 1 4 0 5 2 6

Post-order traversal

1
2
3
4
5
6
7
8
9
10
11
12
def post_order_traverse(node):
    if node == None:
        return

    post_order_traverse(node.left)
    post_order_traverse(node.right)
    print(f"{node.val} ", end="")

post_order_traverse(root)
print()

#Output: 7 8 3 4 1 5 6 2 0

Get tree size

1
2
3
4
5
6
7
8
9
10
def size(node):
    if node == None:
        return 0

    return size(node.left) + 1 + size(node.right)

print(f"size: {size(root)}")
    
#Output:
#size: 9

Get tree depth

1
2
3
4
5
6
7
8
9
10
def depth(node):
    if node == None:
        return 0

    return max(depth(node.left), depth(node.right)) + 1

print(f"depth: {depth(root)}")
    
#Output:
#depth: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def printPaths(node, path):
    if node == None:
        return

    # add node to the path
    path.append(node.val)

    if node.left == None and node.right == None:
        # this is leaf node
        print("path : ", end="")
        for n in path:
            print(f"{n} ", end="")
        print()
    else:
        # search left subtree
        printPaths(node.left, path)

        # search right subtree
        printPaths(node.right, path)

    # remove node from path
    path.pop()
    
printPaths(root, list())

#Output:
#path : 0 1 3 7
#path : 0 1 3 8
#path : 0 1 4
#path : 0 2 5
#path : 0 2 6

Check if path exists for target sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def hasPathSum(node, sum):
    if node == None:
        return sum == 0

    sum -= node.val

    return hasPathSum(node.left, sum) or hasPathSum(node.right, sum)
    
print(hasPathSum(root, 7))
print(hasPathSum(root, 12))
print(hasPathSum(root, 10))
    
#Output:
#True
#True
#False