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

[Leetcode 114] Flatten Binary Tree to Linked List

he root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Solution：

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
36
37
38
39
40
41
42
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # Refer to https://leetcode.com/problems/flatten-binary-tree-to-linked-list/solutions/1208004/extremely-intuitive-o-1-space-solution-with-simple-explanation-python/?envType=study-plan-v2&envId=top-interview-150
    #         1(curr)        1          1  
    #       /   \           /            \
    #      2     5   -->   2      -->     2
    #     / \     \       / \            / \
    #    3   4(p)  6     3   4(p)       3   4
    #                         \              \
    #                          5              5 
    #                           \              \
    #                            6              6
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        curr = root

        while curr:
            if curr.left != None:
                p = curr.left

                # find the right most node of currnt left subtree
                while p.right != None:
                    p = p.right

                # shift the contents of currnt right subtree to p.right
                p.right = curr.right

                # shift the contents of current left subtree to curr.right
                curr.right = curr.left

                # set curr.left to None
                curr.left = None

            # repeat the above process
            curr = curr.right