DSA Trees

A tree is a hierarchical, non-linear data structure that represents data in a parent-child relationship. Unlike arrays and linked lists which store data in a linear sequence, trees allow data to branch out in multiple directions, making them ideal for representing hierarchical relationships such as file systems, organizational charts, and HTML DOM structures.

Core Terminology

  • Node — Each element in the tree that holds data.
  • Root — The topmost node with no parent. Every tree has exactly one root.
  • Parent — A node that has one or more child nodes.
  • Child — A node connected below a parent node.
  • Leaf — A node with no children (end of a branch).
  • Edge — The connection (link) between a parent and child.
  • Height — The longest path from root to a leaf.
  • Depth — The distance of a node from the root.
  • Subtree — A portion of the tree rooted at any node.

Binary Trees

A binary tree is a tree where each node has at most two children, referred to as the left child and the right child. Binary trees are the most commonly studied type of tree in DSA.

Building a Binary Tree Node in Python


class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None    # Left child
        self.right = None   # Right child

Creating a Simple Binary Tree


# Constructing this tree:
#         10
#        /  \
#       5    15
#      / \     \
#     3   7    20

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(20)

Tree Traversal

Tree traversal means visiting every node in the tree exactly once. There are several orders in which nodes can be visited.

1. Inorder Traversal (Left → Root → Right)

In a Binary Search Tree, inorder traversal gives nodes in sorted (ascending) order.


def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.data, end=" ")
    inorder(node.right)

inorder(root)   # Output: 3 5 7 10 15 20

2. Preorder Traversal (Root → Left → Right)

Visits the root before its children. Useful for copying a tree or evaluating prefix expressions.


def preorder(node):
    if node is None:
        return
    print(node.data, end=" ")
    preorder(node.left)
    preorder(node.right)

preorder(root)   # Output: 10 5 3 7 15 20

3. Postorder Traversal (Left → Right → Root)

Visits children before the root. Used for deleting a tree or computing directory sizes.


def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end=" ")

postorder(root)   # Output: 3 7 5 20 15 10

4. Level Order Traversal (Breadth-First)

Visits nodes level by level, from top to bottom. Uses a queue.


from collections import deque

def level_order(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

level_order(root)   # Output: 10 5 15 3 7 20

Binary Search Tree (BST)

A Binary Search Tree is a binary tree with a special ordering property:

  • Every node in the left subtree has a value less than the current node.
  • Every node in the right subtree has a value greater than the current node.

This property makes searching, insertion, and deletion efficient.

Inserting into a BST


def insert(root, data):
    if root is None:
        return TreeNode(data)
    if data < root.data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)
    return root

bst = None
for val in [50, 30, 70, 20, 40, 60, 80]:
    bst = insert(bst, val)

inorder(bst)   # Output: 20 30 40 50 60 70 80 (sorted!)

Searching in a BST — O(log n) average


def search_bst(root, target):
    if root is None:
        return False
    if root.data == target:
        return True
    elif target < root.data:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)

print(search_bst(bst, 40))   # Output: True
print(search_bst(bst, 99))   # Output: False

Tree Height and Depth


def tree_height(node):
    if node is None:
        return 0
    left_height = tree_height(node.left)
    right_height = tree_height(node.right)
    return 1 + max(left_height, right_height)

print("Height:", tree_height(root))   # Output: Height: 3

Types of Trees

Full Binary Tree

Every node has either 0 or 2 children — no node has exactly 1 child.

Complete Binary Tree

All levels are fully filled except possibly the last, which is filled from left to right. Heaps are complete binary trees.

Balanced Binary Tree

The height difference between the left and right subtrees of any node is at most 1. Balanced trees ensure O(log n) operations.

Degenerate (Skewed) Tree

Every parent has only one child. Essentially a linked list. Search becomes O(n) — the worst case for BSTs.

Big O Summary for Binary Search Trees

  • Search — O(log n) average, O(n) worst (skewed tree)
  • Insert — O(log n) average, O(n) worst
  • Delete — O(log n) average, O(n) worst
  • Traversal — O(n) for all traversal methods

Key Points

  • A tree is a hierarchical data structure with a root at the top and leaves at the bottom.
  • Binary trees restrict each node to at most two children.
  • BSTs maintain sorted order, enabling O(log n) search, insert, and delete on balanced trees.
  • Inorder traversal of a BST produces values in sorted ascending order.
  • Four traversal methods exist: inorder, preorder, postorder, and level-order.
  • A skewed BST degrades to O(n) — balanced trees (like AVL or Red-Black) fix this issue.
Previous lessons
Back to courses
Next lessons

Leave a Comment