Trees & Graphs

Trees are hierarchical structures. Graphs are networks of connected nodes.

Tree Types

• Binary Tree — max 2 children
• BST — left < parent < right
• AVL — self-balancing BST

Syntax

COMPUTER-SCIENCE

1
2
3
4
5
6

# Binary Search Tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Binary Tree

PYTHON

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(node):
    if node:
        inorder(node.left)
        print(node.val, end=" ")
        inorder(node.right)

# Build tree
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

print("Inorder traversal:")
inorder(root)  # 1 2 3 4 6

Try It Yourself

Practice

1

Exercise

What is the time complexity of searching in a balanced BST?

Answer

O(log n) — each comparison halves the search space.

Quick Quiz

1

In a BST, where are smaller values stored?

Right subtree

Left subtree

Root

Leaf nodes

In a BST, left children are smaller than parent.

Retry Quiz

Interview Questions

What is the difference between a tree and a graph?

A tree is a hierarchical structure with no cycles. A graph can have cycles and multiple connections between nodes.

Previous

Arrays & Linked Lists

Tutorial Complete

Back to Computer Science