24  Binary Trees Revisited — Structure, Traversals, BST

25 Binary Trees Revisited

Week 1, Session 2. CSS 343.

25.1 Warmup

Find the Middle Index in Array again. (Repeating the 342 warmup once more for safety. Last time.)

25.2 Learning objectives

  1. Define and distinguish height, depth, and size of a binary tree.
  2. Trace all four traversal orders (in, pre, post, level) on a drawn tree.
  3. Write recursive functions for height(node) and size(node).
  4. Implement BST insert and find recursively and explain O(h).

25.3 Vocabulary, with diagrams

              50           depth 0   height 2
             /  \
           30    70        depth 1   height 1
          /  \    \
        20  40    80       depth 2   height 0   <- leaves
  • Depth of a node: edges from root. The root has depth 0.
  • Height of a node: edges to the deepest leaf below it. Leaves have height 0.
  • Height of the tree: height of the root.
  • Size: number of nodes.

Some textbooks use depth = 1 for the root. I use depth = 0 in this book. Either is fine if you are consistent. Read the prompt.

25.4 TreeNode

struct TreeNode {
  int data;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int v) : data(v), left(nullptr), right(nullptr) {}
};

25.5 Recursive properties

int size(TreeNode* node) {
  if (node == nullptr) return 0;
  return 1 + size(node->left) + size(node->right);
}

int height(TreeNode* node) {
  if (node == nullptr) return -1;
  return 1 + max(height(node->left), height(node->right));
}

int countLeaves(TreeNode* node) {
  if (node == nullptr) return 0;
  if (node->left == nullptr && node->right == nullptr) return 1;
  return countLeaves(node->left) + countLeaves(node->right);
}

Same shape every time:

  1. Base case: nullptr returns a “neutral” value.
  2. Recursive case: combine the answers from children.

This is post-order computation: you need the children’s answers before you can compute the parent’s.

25.6 Four traversals

Three recursive (from 342) plus one new — level-order, also called BFS.

void inOrder(TreeNode* node) {
  if (node == nullptr) return;
  inOrder(node->left);
  cout << node->data << " ";
  inOrder(node->right);
}

void preOrder(TreeNode* node) {
  if (node == nullptr) return;
  cout << node->data << " ";
  preOrder(node->left);
  preOrder(node->right);
}

void postOrder(TreeNode* node) {
  if (node == nullptr) return;
  postOrder(node->left);
  postOrder(node->right);
  cout << node->data << " ";
}

void levelOrder(TreeNode* root) {
  if (root == nullptr) return;
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    TreeNode* curr = q.front();
    q.pop();
    cout << curr->data << " ";
    if (curr->left != nullptr) q.push(curr->left);
    if (curr->right != nullptr) q.push(curr->right);
  }
}

Level-order uses a queue. It is iterative, not recursive. Each node is enqueued once, dequeued once, and visited as it leaves the queue.

On the tree from the diagram:

Traversal Order
In-order 20 30 40 50 70 80
Pre-order 50 30 20 40 70 80
Post-order 20 40 30 80 70 50
Level-order 50 30 70 20 40 80

In-order on a BST always produces sorted output — the smell test.

25.7 BST insert and find

void insert(TreeNode*& root, int value) {
  if (root == nullptr) {
    root = new TreeNode(value);
    return;
  }
  if (value < root->data) insert(root->left, value);
  else if (value > root->data) insert(root->right, value);
  // duplicate: ignore (or you can choose to allow duplicates)
}

bool find(TreeNode* root, int value) {
  if (root == nullptr) return false;
  if (value == root->data) return true;
  if (value < root->data) return find(root->left, value);
  return find(root->right, value);
}

Both are O(h). For a balanced tree h = O(log n). For a degenerate one (chapter 17), h = O(n).

25.8 Why TreeNode*& matters in insert

Without the reference:

void insert(TreeNode* root, int value) {        // ← no &
  if (root == nullptr) {
    root = new TreeNode(value);                 // ← only modifies the LOCAL copy
    return;
  }
  // ...
}

Calling insert(myTree, 10) when myTree is nullptr will allocate a node and assign it to the local parameter. The caller’s myTree is unchanged. The new node leaks. Always pass the pointer by reference when you might change which node it points to.

25.9 Try it

Write bool isBalanced(TreeNode*) that returns true if every node’s left and right subtrees differ in height by at most 1.

Naive O(n²) version: recurse, check height of each subtree. Better O(n) version: compute height and bail out (return -1 sentinel) the moment imbalance is found. Try the naive version first.

bool isBalanced(TreeNode* node) {
  if (node == nullptr) return true;
  int diff = abs(height(node->left) - height(node->right));
  if (diff > 1) return false;
  return isBalanced(node->left) && isBalanced(node->right);
}

25.10 Self-check

1. Level-order traversal uses:
c. Push root, then while-not-empty: dequeue, visit, enqueue children. FIFO order produces the level-by-level traversal.
2. height(nullptr) in the convention used here is:
a. So that a single leaf has height 1 + max(-1, -1) = 0.

25.11 Challenges

  1. Binary Tree Inorder Traversal (#94) — recursive and iterative with stack.
  2. Binary Tree Level Order Traversal (#102) — level-order producing vector<vector<int>> per level.
  3. Validate Binary Search Tree (#98) — recurse with min/max bounds.

25.12 Where this fits

We have the data structure. Next, the operation that does not fit on one slide: BST delete.

You are here Coming up
Traversals (in/pre/post/level), insert, find, height/size Chapter 23: BST delete and path problems