Suggest an edit

Improve this article

Refine the answer for “What is a binary tree?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A binary tree is a data structure in which every node has at most two children: a left one and a right one. It's the foundation for a range of structures (a binary search tree, a heap), and is used to store hierarchies and to perform search/insert/delete efficiently when additional properties hold.

## Detailed answer

### Definition and intuition

A binary tree is a connected, acyclic, hierarchical structure of nodes where each node has at most two descendants. Each node stores a value and references to a left and a right child. In general, a binary tree places no constraint on the order of values; ordering is imposed only by specialized variants (for example, a binary search tree).

### Terms and properties

- Node, root, edge, leaf: the basic parts of a tree. A leaf is a node with no children.
- A node's depth is the distance (number of edges) from the root; a node's height is the length of the longest path to a leaf; a tree's height is the height of its root; size is the number of nodes.
- Classifications: perfect, all levels are completely filled; complete, all levels except the last are full, and the last fills left to right; full, every node has either 0 or 2 children; balanced, height O(log n).
- Specializations: a binary search tree (BST), all keys in the left subtree < the node's key < all keys in the right subtree; a heap, a parent's value is not less/not greater (max/min) than its children's values, but the relative order of left/right is undefined.
- Representation in memory: pointer-based (nodes with references), universal; array-based, efficient for complete/nearly complete trees: for index i: left = 2i + 1, right = 2i + 2, parent = ⌊(i - 1) / 2⌋.

### Operations and traversals

1. Preorder (N-L-R): the node first, then the left and right subtree. Useful for copying/serialization.
2. Inorder (L-N-R): left, node, right. For a BST this gives a sorted sequence.
3. Postorder (L-R-N): left, right, node. Useful for deletion/evaluating expressions (expression trees).
4. Level-order (BFS): left to right by level. Suited for problems where "width" matters (for example, shortest path by edges of equal cost).

### Example: building a tree and traversing it (JavaScript)

```
class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Example tree (also a valid BST):
//         8
//       /   \
//      3     10
//     / \      \
//    1   6      14
//       / \    /
//      4   7  13
const root = new Node(
  8,
  new Node(3, new Node(1), new Node(6, new Node(4), new Node(7))),
  new Node(10, null, new Node(14, new Node(13), null))
);

function preorder(node, res = []) {
  if (!node) return res;
  res.push(node.val);
  preorder(node.left, res);
  preorder(node.right, res);
  return res;
}

function inorder(node, res = []) {
  if (!node) return res;
  inorder(node.left, res);
  res.push(node.val);
  inorder(node.right, res);
  return res;
}

function postorder(node, res = []) {
  if (!node) return res;
  postorder(node.left, res);
  postorder(node.right, res);
  res.push(node.val);
  return res;
}

function levelOrder(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const n = q.shift();
    res.push(n.val);
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  return res;
}

console.log('Preorder:', preorder(root).join(' '));
console.log('Inorder:', inorder(root).join(' '));
console.log('Postorder:', postorder(root).join(' '));
console.log('Level-order:', levelOrder(root).join(' '));
```

### BST: insertion and search (JavaScript)

```
function insert(root, val) {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function search(root, val) {
  let cur = root;
  while (cur) {
    if (val === cur.val) return true;
    cur = val < cur.val ? cur.left : cur.right;
  }
  return false;
}

let bst = null;
bst = insert(bst, 8);
[3, 10, 1, 6, 14, 4, 7, 13].forEach(v => (bst = insert(bst, v)));
console.log('Search 7:', search(bst, 7)); // true
console.log('Search 2:', search(bst, 2)); // false
```

### Checking properties: BST validity and balance

```
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.val <= min || node.val >= max) return false;
  return (
    isValidBST(node.left, min, node.val) &&
    isValidBST(node.right, node.val, max)
  );
}

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;
    const lh = height(node.left);
    if (lh === -1) return -1;
    const rh = height(node.right);
    if (rh === -1) return -1;
    if (Math.abs(lh - rh) > 1) return -1;
    return Math.max(lh, rh) + 1;
  }
  return height(root) !== -1;
}

console.log('Valid BST:', isValidBST(bst));
console.log('Balanced:', isBalanced(bst));
```

### Diagram and traversal results

```
Tree:
         8
       /   \
      3     10
     / \      \
    1   6      14
       / \    /
      4   7  13

Preorder (N-L-R):   8 3 1 6 4 7 10 14 13
Inorder (L-N-R):    1 3 4 6 7 8 10 13 14
Postorder (L-R-N):  1 4 7 6 3 13 14 10 8
Level-order (BFS):  8 3 10 1 6 14 4 7 13
```

### Complexity

| Operation | General case | BST (average) | BST (worst) | Memory |
|---|---|---|---|---|
| Traversals (DFS/BFS) | O(n) | - | - | O(h) stack or O(n) queue |
| Search (BST) | - | O(log n) | O(n) | O(1) |
| Insert (BST) | - | O(log n) | O(n) | O(1) |
| Delete (BST) | - | O(log n) | O(n) | O(1) |
| Access to children/parent (array) | O(1) | O(1) | O(1) | O(1) |

### When to use it

- Parsers and parse trees (AST), expression trees.
- Priority queues (a binary heap).
- Fast search/insert/delete in an ordered collection (BST, self-balancing trees).
- Decision trees, routing, database indexes (variations of B-trees, though they aren't binary).

### Common interview questions

- How does a binary tree differ from a BST? In a BST, values are ordered by the property left < node < right; in a general binary tree there may be no order.
- Why does an inorder traversal of a BST produce a sorted sequence? It visits the left subtree (all smaller values), then the node, then the right subtree (all larger values).
- What's the difference between height and depth? Depth is from the root to a node; height is from a node to its deepest leaf.
- Balanced vs complete vs perfect? Balanced: height O(log n); complete: the last level fills left to right; perfect: all levels completely filled.
- How do you represent a tree as an array? For index i: left = 2i + 1, right = 2i + 2, parent = ⌊(i - 1) / 2⌋ (suits complete trees).

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1097 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.