Binary Tree

A binary tree is a hierarchical data structure where every node holds a value and has at most two children, conventionally called left and right. The top node is the root, and nodes with no children are leaves.

Why it matters

Trees model hierarchical data and enable fast searching. In a binary search tree (BST), values in the left subtree are smaller than the node and values in the right subtree are larger, so each comparison discards about half the remaining nodes, giving O(log n) lookup when the tree is balanced. If values are inserted in sorted order, a plain BST degenerates into a linked list with O(n) operations, which is why balanced variants such as AVL and red-black trees exist. Heaps, expression parsers and many database indexes (B-trees, a multiway relative) build on tree ideas.

Example

class Node:
    def __init__(self, v): self.v, self.l, self.r = v, None, None

def contains(node, x):
    if node is None: return False
    if x == node.v: return True
    return contains(node.l if x < node.v else node.r, x)

Common mistakes

• Assuming a BST is always balanced.
• Recursing on very deep trees and overflowing the stack.
• Confusing a binary tree with a binary search tree, which has an ordering rule.

Related

• Recursion
• Database index
• Linked list
• Data structure

This page is general information written by our editorial team and updated when documentation changes. Servers and providers differ, so test changes safely first. See our editorial policy and disclaimer.