Skip to content
Concept ยท Data Structures and Algorithms

Tree Data Structure Explained: Binary Trees, BST, Traversals and Height, With Python and JavaScript Code

By Younus FardeenUpdated 11 Nov 202611 min read
Short answer

A tree is a hierarchical data structure with one root node, where each node has zero or more children and there are no cycles. A binary tree allows at most two children per node. A binary search tree (BST) keeps smaller keys on the left and larger on the right, giving O(log n) search on average but O(n) if lopsided.

Trees are the first non-linear structure most learners meet, and they turn up in interviews constantly. This page covers the vocabulary, the main types, a working binary search tree in Python and JavaScript with all four traversals, and why balance decides whether a tree is fast.

Every code block was run on Python 3.9 and Node 24 on 11 November 2026 and the output shown is the real output. Height and depth definitions follow Wikipedia's tree page, read on the same date.

What a tree is

A tree is a collection of nodes joined by edges with one special node at the top, the root. Every other node has exactly one parent, and a node can have any number of children. There are no cycles, so there is exactly one path between any two nodes. In graph language, a tree is a connected, acyclic graph, and n nodes always have n - 1 edges.

TermMeaning
RootThe top node, with no parent
LeafA node with no children
SubtreeA node together with all its descendants
Depth of a nodeNumber of edges from the root down to that node (the root has depth 0)
Height of a nodeNumber of edges on the longest path down to a leaf (a leaf has height 0)
Height of the treeThe height of the root
LevelAll nodes at the same depth

Here height is counted in edges, so a single-node tree has height 0 and an empty tree has height -1. Some textbooks and interview platforms count nodes instead, which adds 1. Check which your course or problem uses.

Trees are everywhere in software: folders inside folders, the HTML page that your browser holds as a tree of elements (MDN calls it the Document Object Model), JSON documents, organisation charts, and the expression trees that compilers build.

Types of trees in data structure

TypeRuleWhere it is used
General treeAny number of children per nodeFolders, organisation charts, the page structure of a website
Binary treeAt most two children, called left and rightThe base for most tree problems
Full binary treeEvery node has 0 or 2 childrenExpression trees
Complete binary treeEvery level is full except possibly the last, which fills from the leftHeaps
Perfect binary treeAll leaves at the same depth and every other node has 2 childrenAnalysis: height h holds 2^(h+1) - 1 nodes
Binary search tree (BST)Left subtree keys < node key < right subtree keysOrdered data with fast search
Self-balancing BST (AVL, red-black)A BST that rebalances itself so height stays O(log n)Ordered maps and sets in standard libraries
HeapA complete tree where each parent is smaller (min-heap) or larger (max-heap) than its childrenPriority queues
Trie (prefix tree)Each edge is a character, so words with a shared prefix share a pathAutocomplete, spell checkers
B-treeA wide balanced tree with many keys per nodeDatabase and file-system indexes

Binary search tree: insert, search and the four traversals

In a binary search tree every key in a node's left subtree is smaller than the node, and every key in its right subtree is larger. To search, compare with the current node and go left or right, discarding about half the remaining tree at each step when the tree is balanced. The code builds one tree, prints it in four orders and searches it.

from collections import deque

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)       # equal keys are ignored
    return root

def search(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None

def inorder(n):                                    # left, node, right
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []

def preorder(n):                                   # node, left, right
    return [n.key] + preorder(n.left) + preorder(n.right) if n else []

def postorder(n):                                  # left, right, node
    return postorder(n.left) + postorder(n.right) + [n.key] if n else []

def level_order(root):                             # level by level, with a queue
    out, queue = [], deque([root])
    while queue:
        n = queue.popleft()
        out.append(n.key)
        for child in (n.left, n.right):
            if child:
                queue.append(child)
    return out

def height(n):                                     # counted in edges; a leaf is 0
    return -1 if n is None else 1 + max(height(n.left), height(n.right))

root = None
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, k)

print("inorder    ", inorder(root))
print("preorder   ", preorder(root))
print("postorder  ", postorder(root))
print("level order", level_order(root))
print("height", height(root), "| has 6:", search(root, 6), "| has 5:", search(root, 5))

Output:

inorder     [1, 3, 4, 6, 7, 8, 10, 13, 14]
preorder    [8, 3, 1, 6, 4, 7, 10, 14, 13]
postorder   [1, 4, 7, 6, 3, 13, 14, 10, 8]
level order [8, 3, 10, 1, 6, 14, 4, 7, 13]
height 3 | has 6: True | has 5: False

The same tree in JavaScript:

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

function insert(root, key) {
  if (!root) return new Node(key);
  if (key < root.key) root.left = insert(root.left, key);
  else if (key > root.key) root.right = insert(root.right, key);   // equal keys are ignored
  return root;
}

function search(root, key) {
  while (root && root.key !== key) root = key < root.key ? root.left : root.right;
  return root !== null;
}

const inorder = (n) => (n ? [...inorder(n.left), n.key, ...inorder(n.right)] : []);
const preorder = (n) => (n ? [n.key, ...preorder(n.left), ...preorder(n.right)] : []);
const postorder = (n) => (n ? [...postorder(n.left), ...postorder(n.right), n.key] : []);

function levelOrder(root) {
  const out = [];
  const queue = [root];
  for (let i = 0; i < queue.length; i++) {
    out.push(queue[i].key);
    if (queue[i].left) queue.push(queue[i].left);
    if (queue[i].right) queue.push(queue[i].right);
  }
  return out;
}

let root = null;
for (const k of [8, 3, 10, 1, 6, 14, 4, 7, 13]) root = insert(root, k);

console.log("inorder    ", inorder(root).join(" "));
console.log("preorder   ", preorder(root).join(" "));
console.log("postorder  ", postorder(root).join(" "));
console.log("level order", levelOrder(root).join(" "));
console.log("has 6:", search(root, 6), "| has 5:", search(root, 5));

Output:

inorder     1 3 4 6 7 8 10 13 14
preorder    8 3 1 6 4 7 10 14 13
postorder   1 4 7 6 3 13 14 10 8
level order 8 3 10 1 6 14 4 7 13
has 6: true | has 5: false

Which traversal to use

TraversalOrder of visitTypical use
Inorder (DFS)Left, node, rightOn a BST it returns the keys in sorted order, as the first line above shows
Preorder (DFS)Node, left, rightCopying or saving a tree, because parents come before children
Postorder (DFS)Left, right, nodeDeleting a tree or evaluating an expression, because children come first
Level order (BFS)Level by level, using a queueShortest depth, per-level answers, printing a tree by rows

The three DFS orders are naturally recursive, so recursion is the key skill. Level order is breadth-first search and uses a queue (see applications of queue). Every traversal visits each node once, so each takes O(n) time.

Why balance matters: height decides speed

Search, insert and delete all walk from the root down one path, so their cost is the tree's height. Insert the keys 1 to 127 in sorted order and every key goes to the right, so the tree becomes a linked list. Insert the same keys middle first and it stays short:

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

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

def height(n):
    return -1 if n is None else 1 + max(height(n.left), height(n.right))

def middle_first(lo, hi):
    """Yield lo..hi so that the middle value comes first, then each half the same way."""
    if lo > hi:
        return
    mid = (lo + hi) // 2
    yield mid
    yield from middle_first(lo, mid - 1)
    yield from middle_first(mid + 1, hi)

sorted_tree = balanced_tree = None
for k in range(1, 128):                      # same 127 keys, two insertion orders
    sorted_tree = insert(sorted_tree, k)
for k in middle_first(1, 127):
    balanced_tree = insert(balanced_tree, k)

print("sorted order:", height(sorted_tree), "| middle first:", height(balanced_tree))

Output: sorted order: 126 | middle first: 6

Same data, but a height of 126 against 6. A self-balancing tree repairs itself after each insert so this cannot happen. An AVL tree, for instance, keeps the heights of the two subtrees of every node within one of each other, and Java's TreeMap is a red-black tree with guaranteed O(log n) search, insert and remove (see the Java documentation). Python's standard library has no balanced tree type, so people use dictionaries, sorted lists with bisect, or a third-party package.

OperationPlain BST, averagePlain BST, worst caseBalanced BST (AVL, red-black)
SearchO(log n)O(n)O(log n)
InsertO(log n)O(n)O(log n)
DeleteO(log n)O(n)O(log n)
Traverse all nodesO(n)O(n)O(n)
SpaceO(n)O(n)O(n)

The worst case for a plain BST comes from sorted or nearly sorted input, which is common in real data. Databases use a related idea: PostgreSQL's CREATE INDEX makes a B-tree index by default.

Two special trees: heap and trie

A heap stores a tree in a list so the smallest item (min-heap) is always first, which makes a priority queue. A trie gives each letter its own node so that finding every word with a given prefix is a walk down the tree. Both fit in a few lines:

import heapq

# Heap: a tree stored in a list, where the smallest item is always at index 0
tasks = [5, 1, 4, 2]
heapq.heapify(tasks)
print(heapq.heappop(tasks), heapq.heappop(tasks))

# Trie: one node per letter, so words that share a prefix share a path
trie = {}
for word in ["car", "card", "care", "cat", "dog"]:
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})
    node["$"] = True                         # marks the end of a word

def with_prefix(prefix):
    node = trie
    for ch in prefix:
        if ch not in node:
            return []
        node = node[ch]
    found = []
    def walk(n, path):
        for ch, child in sorted(n.items()):
            if ch == "$":
                found.append(prefix + path)
            else:
                walk(child, path + ch)
    walk(node, "")
    return found

print(with_prefix("car"), with_prefix("x"))

Output:

1 2
['car', 'card', 'care'] []

The heap popped 1 then 2, the two smallest of [5, 1, 4, 2]. The trie returned the three words that start with car and nothing for x. Python's heapq module is documented in the standard library reference.

Common mistakes and practice problems

Common mistakes

  • Mixing up height and depth, or counting nodes when the question counts edges.
  • Forgetting the empty-tree case. Every recursive function needs a base case for a missing child.
  • Assuming a BST is always O(log n). Sorted input turns it into a list, as the example above shows.
  • Validating a BST by checking only each node against its direct children. Every node must fall inside the range set by all its ancestors.
  • Changing the tree while traversing it without a plan for what the loop will see next.
  • Deep recursion on a skewed tree. A tree 5,000 levels deep can exceed Python's default recursion limit of about 1,000, so use an explicit stack or queue.

Practice problems, in order

  1. Maximum Depth of Binary Tree
  2. Invert Binary Tree
  3. Binary Tree Inorder Traversal (try it without recursion)
  4. Binary Tree Level Order Traversal
  5. Validate Binary Search Tree
  6. Lowest Common Ancestor of a Binary Search Tree
  7. Kth Smallest Element in a BST
  8. Diameter of Binary Tree
  9. Construct Binary Tree from Preorder and Inorder Traversal
  10. Implement Trie (Prefix Tree)

Masai's longer guides: Tree Data Structure: Types, Traversal, Operations, Code and Applications of Tree Explained. Next, read graph data structure explained, where a tree is a special case, and the linked list page. For the full order of topics, use the DSA learning path.

Frequently asked questions

What is a tree in data structure?

A tree is a hierarchical structure of nodes with one root, where every other node has exactly one parent and there are no cycles. Examples are a folder structure, the HTML elements of a web page and an organisation chart.

What is the difference between a binary tree and a binary search tree?

A binary tree only limits each node to two children. A binary search tree adds an ordering rule: keys in the left subtree are smaller and keys in the right subtree are larger, which makes searching fast.

What is the height of a tree?

The number of edges on the longest path from the root down to a leaf. A single node has height 0 and an empty tree has height -1. Some sources count nodes instead, which gives a value one larger, so check the definition in use.

What is the difference between inorder, preorder and postorder traversal?

They differ in when the node is visited relative to its subtrees: preorder visits node, left, right; inorder visits left, node, right; postorder visits left, right, node. Inorder on a BST gives sorted keys.

What is a balanced tree and why does it matter?

A balanced tree keeps its height close to log n, for example AVL trees that keep the two subtrees of every node within one level of each other. Search, insert and delete then stay O(log n) instead of degrading to O(n).

What is the difference between a tree and a graph?

A tree is a graph that is connected and has no cycles, with one path between any two nodes. A general graph may have cycles, several components and many paths.

Where are trees used in real life?

File systems, the HTML structure of web pages, database indexes, parsers and compilers, autocomplete and priority queues all use trees.

Sources checked

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Continue learning

Concept

Graph data structure

Vertices, edges, BFS, DFS and cycle checks with tested code

Open →
Concept

Linked list

Singly, doubly and circular lists, Big-O, and the classic interview patterns

Open →
Explainer

What is recursion?

Base case, call stack and examples, with code in three languages.

Open →