Skip to content

Binary Tree

Binary trees are a fundamental data structure in computer science, where each node has at most two children, referred to as the left and right child. They are used in various applications such as searching, sorting, and representing hierarchical data.

  • Pre Order Traversal (DFS): Visit the root node first, then recursively visit the left subtree, followed by the right subtree.
  • In Order Traversal (DFS): Recursively visit the left subtree first, then visit the root node, followed by the right subtree.
  • Level Order Traversal (BFS): Visit nodes level by level, starting from the root and moving down to the leaves.

Import packages

1
from collections import deque

Define node class

1
2
3
4
5
6
7
8
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.value)

Defining tree

graph TD
    A[1]
    B[2]
    C[3]
    D[4]
    E[5]
    F[10]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)
f = Node(10)

a.left = b
a.right = c
b.left = d
b.right = e
c.left = f

Recursive pre order traversal DFS (Depth First Search)

  • Time complexity: O(n) - Each node is visited once.
  • Space complexity: O(n) - In the worst case (a completely unbalanced tree).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def pre_order(node):
    if not node:
        return

    print(node)
    pre_order(node.left)
    pre_order(node.right)


pre_order(a)

1

2

4

5

3

10

Recursive in order traversal DFS (Depth First Search)

  • Time complexity: O(n) - Each node is visited once.
  • Space complexity: O(n) - In the worst case (a completely unbalanced tree).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def in_order(node):
    if not node:
        return

    in_order(node.left)
    print(node)
    in_order(node.right)


in_order(a)

4

2

5

1

10

3

Interactive pre order traversal DFS (Depth First Search)

  • Time complexity: O(n) - Each node is visited once.
  • Space complexity: O(n) - In the worst case (a completely unbalanced tree).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def pre_order_interactive(node):
    stk = [node]

    while stk:
        node = stk.pop()
        print(node)
        if node.right:
            stk.append(node.right)
        if node.left:
            stk.append(node.left)


pre_order_interactive(a)

1

2

4

5

3

10

Level order traversal BFS (Breadth First Search)

  • Time complexity: O(n) - Each node is visited once.
  • Space complexity: O(n) - In the worst case (a completely unbalanced tree).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def level_order(node):
    queue = deque()
    queue.append(node)

    while queue:
        node = queue.popleft()
        print(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)


level_order(a)

1

2

3

4

5

10

Check if value exists DFS (Depth First Search)

  • Time complexity: O(n) - Each node is visited once.
  • Space complexity: O(n) - In the worst case (a completely unbalanced tree).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def search(node, target):
    if not node:
        return False

    if node.value == target:
        return True

    return search(node.left, target) or search(node.right, target)


search(a, 2)

True