Python Tree Data Structure

A tree is a non-linear data structure used to represent hierarchical data. Examples include file systems, HTML DOM trees, organization charts, menus, search trees, and parser output.

A tree starts with a root node. Each node can have child nodes. Nodes with no children are leaf nodes.

Tested on: Python 3.13.3; kernel 6.14.0-37-generic.

Python tree data structure quick reference

What is a tree data structure in Python?

A tree is a hierarchical, non-linear structure. Python does not ship one built-in universal tree class—you usually build trees with:

• Custom classes
• Dictionaries and lists
• Third-party libraries such as anytree or bigtree for richer features

A tree has one root, and each child can have its own children. That parent-child layout is useful whenever data is nested rather than flat.

Common examples of trees

Trees appear in many everyday structures:

• File system folders — directories contain subdirectories and files.
• HTML or XML — elements nest inside other elements.
• Organization charts — managers and teams form a hierarchy.
• Menus and submenus — options branch into deeper choices.
• Comments and replies — threads form a tree of responses.
• Binary search tree — ordered data for fast lookup.
• Expression tree — operators and operands in parsers.
• Trie — prefixes for words and autocomplete.

Understanding these examples helps before you write node classes.

Basic tree terminology

• Root — the top node; every other node is reachable from it.
• Parent — a node that has one or more children below it.
• Child — a node directly below another node.
• Sibling — nodes that share the same parent.
• Leaf — a node with no children.
• Edge — the connection between a parent and a child.
• Path — the sequence of nodes and edges from one node to another.
• Subtree — a node plus all of its descendants.
• Depth — number of edges from the root to a node.
• Height — longest path from a node down to a leaf.

Types of trees in data structure

This page focuses on general trees, binary trees, and binary search trees (BST). For a full BST implementation with insert, search, delete, and complexity notes, see implement a binary search tree in Python.

Ways to implement a tree in Python

Class-based nodes are the clearest way to learn trees: each node stores a value and references to children.

Dictionary or list representation works for small trees or JSON-like data:

tree = {
    "value": "root",
    "children": [
        {"value": "left", "children": []},
        {"value": "right", "children": []},
    ],
}

Libraries such as anytree or bigtree help when you need parent links, rendering, search helpers, or export—useful in real projects beyond learning exercises.

For learning data structures, start with a simple Node class. Reach for a library when the tree grows or needs tooling around it.

Create a simple tree node in Python

A node stores data and references to children:

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []      # general tree
        self.left = None        # binary tree
        self.right = None       # binary tree

For a general tree, keep children in a list. For a binary tree, use left and right only.

General tree implementation in Python

A general tree node can have many children. This pattern fits menus, folders, and comment threads:

class GeneralNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)


root = GeneralNode("Home")
root.add_child(GeneralNode("Products"))
root.add_child(GeneralNode("Contact"))

for child in root.children:
    print(child.value)

The loop prints Products then Contact.

Binary tree implementation in Python

A binary tree node has at most two children: left and right. Values are not automatically sorted—that comes later with a BST.

root
       /    \
   left    right

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


root = BinaryNode("A")
root.left = BinaryNode("B")
root.right = BinaryNode("C")

print(root.value, root.left.value, root.right.value)

The output is A B C.

Binary tree vs binary search tree

A binary tree is the base shape. A BST adds ordering rules on top.

Binary search tree in Python

A binary search tree (BST) is a binary tree where:

• Values in the left subtree are smaller than the current node.
• Values in the right subtree are greater than the current node (or greater-or-equal if you choose that duplicate policy).

Define duplicate handling explicitly—this tutorial sends equal values to the right subtree.

Insert nodes in a binary search tree

Insertion steps:

1. If the tree is empty, the new value becomes the root.
2. Compare the new value with the current node.
3. Go left if smaller, right if greater or equal.
4. Insert when an empty child slot is found.

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = BinaryNode(value)
            return

        node = self.root
        while True:
            if value < node.value:
                if node.left is None:
                    node.left = BinaryNode(value)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = BinaryNode(value)
                    return
                node = node.right


bst = BinarySearchTree()
for value in (10, 5, 20, 30, 25, 2):
    bst.insert(value)

The tree stores 10 as root with 5 and 20 below, then deeper nodes for 2, 30, and 25.

Tree traversal in Python

Tree traversal means visiting every node in a specific order.

The example below builds a BST and runs every traversal plus search in one program. Use Run on this block to execute the full demo in one pass; other snippets on this page are shorter copy-and-study examples.

from collections import deque


class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = BinaryNode(value)
            return
        node = self.root
        while True:
            if value < node.value:
                if node.left is None:
                    node.left = BinaryNode(value)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = BinaryNode(value)
                    return
                node = node.right


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


def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")


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


def search(root, target):
    node = root
    while node:
        if target == node.value:
            return True
        node = node.left if target < node.value else node.right
    return False


bst = BinarySearchTree()
for value in (10, 5, 20, 30, 25, 2):
    bst.insert(value)

print("inorder:", end=" ")
inorder(bst.root)
print("\npreorder:", end=" ")
preorder(bst.root)
print("\npostorder:", end=" ")
postorder(bst.root)
print("\nlevel:", end=" ")
level_order(bst.root)
print("\nsearch 25:", search(bst.root, 25))
print("search 99:", search(bst.root, 99))

Inorder prints sorted values 2 5 10 20 25 30. Preorder starts at the root (10 5 2 20 30 25). Postorder ends at the root (2 5 25 30 20 10). Level-order visits top to bottom (10 5 20 2 30 25). Search finds 25 and misses 99.

The sections below explain each method in more detail. All walkthroughs use this BST shape:

10
      /  \
     5   20
    /     \
   2      30
         /
        25

Inorder traversal

Order: Left → Root → Right

Inorder means you fully explore the left subtree, then handle the current node, then explore the right subtree. On the sample tree above, the visit sequence is:

2 → 5 → 10 → 20 → 25 → 30

Because a BST keeps smaller values on the left and larger values on the right, inorder traversal prints keys in ascending sorted order. That is why inorder is the usual choice when you need sorted output from a BST.

How inorder recursion works

At node 10, Python first recurses into the left subtree (5, then 2), prints values on the way back up, prints 10, then recurses into the right subtree (20, 25, 30). The base case is an empty node (None), which stops recursion.

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


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


root = BinaryNode(10)
root.left = BinaryNode(5)
root.right = BinaryNode(20)
root.left.left = BinaryNode(2)

print("inorder:", end=" ")
inorder(root)

The output is inorder: 2 5 10 20.

Each recursive call must invoke inorder, not preorder or postorder. Calling the wrong function is a common bug when learning traversals.

When to use inorder

• Print BST values in sorted order.
• Validate that a binary tree satisfies BST ordering (compare output to a sorted copy).
• Process nodes from smallest to largest in ordered search trees.

Preorder traversal

Order: Root → Left → Right

Preorder visits the current node first, then the left subtree, then the right subtree. On the sample tree, the sequence is:

10 → 5 → 2 → 20 → 30 → 25

The root 10 appears first, which makes preorder useful when you want to record structure before details—similar to writing a folder name before listing its contents.

How preorder recursion works

At each node, print the value immediately, then recurse left, then recurse right. If you read the preorder output while rebuilding a tree, you always know which node became the subtree root at each step.

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)


root = BinaryNode(10)
root.left = BinaryNode(5)
root.right = BinaryNode(20)
root.left.left = BinaryNode(2)

print("preorder:", end=" ")
preorder(root)

The output is preorder: 10 5 2 20.

Each recursive call must invoke preorder.

When to use preorder

• Serialize a tree to a list or string and rebuild it later.
• Copy a tree by creating a node before copying its children.
• Print prefix expressions in expression trees (operator before operands).

Postorder traversal

Order: Left → Right → Root

Postorder finishes both subtrees before visiting the root. On the sample tree, the sequence is:

2 → 5 → 25 → 30 → 20 → 10

The root 10 is last because every descendant must be handled first.

How postorder recursion works

Recurse left, recurse right, then print the node. That order matters when an operation on a parent depends on its children already being processed—freeing memory is the classic example.

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")


root = BinaryNode(10)
root.left = BinaryNode(5)
root.right = BinaryNode(20)
root.left.left = BinaryNode(2)

print("postorder:", end=" ")
postorder(root)

The output is postorder: 2 5 20 10.

Each recursive call must invoke postorder.

When to use postorder

• Delete a tree safely (remove children before removing the parent).
• Evaluate postfix expressions in expression trees.
• Compute values bottom-up when parent results depend on child results (for example, directory size from file sizes).

Level-order traversal / BFS

Level-order traversal visits nodes top to bottom, level by level. On the sample tree:

• Level 0: 10
• Level 1: 5, 20
• Level 2: 2, 30
• Level 3: 25

Combined output: 10 5 20 2 30 25

Unlike the three DFS methods, level-order is usually iterative. Enqueue the root, dequeue a node, process it, then enqueue its left and right children. A queue (collections.deque) gives FIFO order so nodes from the same level are processed before deeper levels.

from collections import deque


class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def level_order(root):
    if not root:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)


root = BinaryNode(10)
root.left = BinaryNode(5)
root.right = BinaryNode(20)
root.left.left = BinaryNode(2)
root.right.right = BinaryNode(30)
root.right.right.left = BinaryNode(25)

print("level:", end=" ")
level_order(root)

The output is level: 10 5 20 2 30 25.

When to use level-order

• Print a tree row by row for display.
• Find the shortest path from root to a target in an unweighted tree.
• Process nodes by depth (for example, assign levels in an org chart).

Search in a binary search tree

BST search compares the target with the current node and walks left if the target is smaller or right if it is greater. Stop when the value is found or the path hits None.

Searching for 25 in the sample tree:

1. Start at 10 — 25 is greater, go right.
2. At 20 — 25 is greater, go right.
3. At 30 — 25 is smaller, go left.
4. At 25 — match found.

Searching for 99 follows 10 → 20 → 30, then tries to go right from 30 where no node exists, so the search fails.

class BinaryNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def search(root, target):
    node = root
    while node:
        if target == node.value:
            return True
        node = node.left if target < node.value else node.right
    return False


root = BinaryNode(10)
root.left = BinaryNode(5)
root.right = BinaryNode(20)
root.left.left = BinaryNode(2)
root.right.right = BinaryNode(30)
root.right.right.left = BinaryNode(25)

print(search(root, 25))
print(search(root, 99))
print(search(root, 2))

The first and third calls return True; the second returns False.

Iterative search avoids recursion depth limits on very tall trees. The full combined example earlier in this page uses the same logic inside a BinarySearchTree class.

Time complexity of tree operations

A BST is efficient when it stays balanced. If values are inserted in sorted order, the tree can become a skewed chain and behave like a linked list with O(n) search time.

When should you use a tree?

Trees fit well when data is:

• Hierarchical — folders, menus, org charts, nested comments.
• Searchable with ordering — balanced BSTs or similar structures.
• Prefix-based — tries for autocomplete and dictionaries.
• Priority-based — heaps for priority queues.
• Structured for parsing — expression trees in compilers and calculators.

Use a flat list or dictionary when hierarchy and traversal order are not important.

Common mistakes to avoid

1. Confusing a general tree with a binary tree — binary trees cap children at two.
2. Confusing a binary tree with a BST — only a BST enforces left/right ordering.
3. Forgetting the base case in recursive traversal — always check if node: before recursing.
4. Calling the wrong traversal function inside recursion — preorder must call preorder, not inorder.
5. Using a global root everywhere — prefer a tree class that owns the root pointer.
6. Not defining duplicate handling in a BST — decide whether equal values go left or right.
7. Assuming BST is always O(log n) — unbalanced trees degrade to O(n).
8. Deep recursion on very tall trees — consider iteration or balance strategies for huge depths.

Summary

A tree is a hierarchical data structure with a root, children, and leaves. In Python, trees are usually built with classes or dictionaries. A binary tree has at most two children per node; a BST adds ordering rules for search. Visit nodes with DFS (inorder, preorder, postorder) or BFS (level-order). Choose the structure that matches your data—general tree for open hierarchies, BST when ordered lookup matters.

Useful references

• Python tutorial: Classes
• Implement a binary search tree in Python