---
title: Tree Data Structure: Types, Traversals, BST and Code
url: https://www.masaischool.com/resources/tree-data-structure-explained
description: Tree data structure explained: root, leaf, height, binary tree, BST, inorder, preorder, postorder and level order traversal, and balanced trees, with code.
updated: 2026-11-17
publisher: Masai (https://www.masaischool.com)
---

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

> **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](https://www.masaischool.com/resources/graph-data-structure-explained), and n nodes always have n - 1 edges.

| Term | Meaning |
|---|---|
| Root | The top node, with no parent |
| Leaf | A node with no children |
| Subtree | A node together with all its descendants |
| Depth of a node | Number of edges from the root down to that node (the root has depth 0) |
| Height of a node | Number of edges on the longest path down to a leaf (a leaf has height 0) |
| Height of the tree | The height of the root |
| Level | All 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](https://developer.mozilla.org/en-US/docs/Web/API/Document_Object_Model)), JSON documents, organisation charts, and the expression trees that compilers build.

## Types of trees in data structure

| Type | Rule | Where it is used |
|---|---|---|
| General tree | Any number of children per node | Folders, organisation charts, the page structure of a website |
| Binary tree | At most two children, called left and right | The base for most tree problems |
| Full binary tree | Every node has 0 or 2 children | Expression trees |
| Complete binary tree | Every level is full except possibly the last, which fills from the left | Heaps |
| Perfect binary tree | All leaves at the same depth and every other node has 2 children | Analysis: height h holds 2^(h+1) - 1 nodes |
| Binary search tree (BST) | Left subtree keys < node key < right subtree keys | Ordered 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 |
| Heap | A complete tree where each parent is smaller (min-heap) or larger (max-heap) than its children | Priority queues |
| Trie (prefix tree) | Each edge is a character, so words with a shared prefix share a path | Autocomplete, spell checkers |
| B-tree | A wide balanced tree with many keys per node | Database 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

| Traversal | Order of visit | Typical use |
|---|---|---|
| Inorder (DFS) | Left, node, right | On a BST it returns the keys in sorted order, as the first line above shows |
| Preorder (DFS) | Node, left, right | Copying or saving a tree, because parents come before children |
| Postorder (DFS) | Left, right, node | Deleting a tree or evaluating an expression, because children come first |
| Level order (BFS) | Level by level, using a queue | Shortest depth, per-level answers, printing a tree by rows |

The three DFS orders are naturally recursive, so [recursion](https://www.masaischool.com/resources/what-is-recursion) is the key skill. Level order is breadth-first search and uses a queue (see [applications of queue](https://www.masaischool.com/resources/applications-of-queue-in-data-structure)). 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](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/TreeMap.html)). Python's standard library has no balanced tree type, so people use dictionaries, sorted lists with bisect, or a third-party package.

| Operation | Plain BST, average | Plain BST, worst case | Balanced BST (AVL, red-black) |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) |
| Traverse all nodes | O(n) | O(n) | O(n) |
| Space | O(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](https://www.postgresql.org/docs/current/indexes-types.html).

### 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](https://docs.python.org/3/library/heapq.html).

## 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](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
2. [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
3. [Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) (try it without recursion)
4. [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)
5. [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
6. [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
7. [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
8. [Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)
9. [Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
10. [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)

Masai's longer guides: [Tree Data Structure: Types, Traversal, Operations, Code](https://www.masaischool.com/blog/tree-data-structure-types-operations-applications/) and [Applications of Tree Explained](https://www.masaischool.com/blog/applications-of-tree/). Next, read [graph data structure explained](https://www.masaischool.com/resources/graph-data-structure-explained), where a tree is a special case, and the [linked list](https://www.masaischool.com/resources/linked-list-explained) page. For the full order of topics, use the [DSA learning path](https://www.masaischool.com/resources/data-structures-and-algorithms).

## 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

- [Height counted in edges, depth, leaf and root definitions](https://en.wikipedia.org/wiki/Tree_(abstract_data_type))
- [BST average Theta(log n), worst case O(n)](https://en.wikipedia.org/wiki/Binary_search_tree)
- [AVL: subtree heights differ by at most one](https://en.wikipedia.org/wiki/AVL_tree)
- [Java TreeMap is a red-black tree with guaranteed log(n) get, put, remove](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/TreeMap.html)
- [PostgreSQL creates B-tree indexes by default](https://www.postgresql.org/docs/current/indexes-types.html)
- [The DOM represents a document as a logical tree](https://developer.mozilla.org/en-US/docs/Web/API/Document_Object_Model)
- [Python heapq module](https://docs.python.org/3/library/heapq.html)
- [Existing Masai post (HTTP 200 on 11 Nov 2026)](https://www.masaischool.com/blog/tree-data-structure-types-operations-applications/)
