Skip to content
Tutorials Center
My learning

Topics

Lesson 97 of 225 ยท Trees

Binary Tree Problems: Flatten, Candies, Ancestor Difference, Lonely Nodes

Solve classic binary tree problems in Python: flatten to a linked list, distribute candies, node-ancestor maximum difference, nodes without siblings and BST to min-heap.

You already know how to walk a tree and how to ask a recursive question about its shape. This lesson turns that into a workout: five problems that each need one small twist on the standard recursion. Four are about plain binary trees and one is about a binary search tree.

The twists fall into three families. Return a value upward (a candy balance, a count). Pass a value downward (the smallest and largest value seen on the way from the root). Rewire pointers in place (flatten). Once you can name the family, the code nearly writes itself.

Every example uses the same small node class:

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

Problem 1: Flatten a tree into a linked list

Rewire the tree in place so that every node's right pointer points to the next node in preorder, and every left pointer is None. The result looks like a linked list that happens to use the tree's own fields.

The easy way is to collect the preorder into a list and relink, but that costs O(n) extra memory. The neat way works backwards. Preorder is node, left, right, so its reverse is right, left, node. Visit the nodes in that reverse order and keep a variable prev holding the node that comes after the current one in preorder. For each node, set node.right = prev, node.left = None, then prev = node. Because each node is only relinked after its successor is known, nothing is lost.

Python Flatten with a reverse walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), extra space O(h) for the recursion only. An iterative version needs O(1) extra space and is closely related to Morris traversal: at each node that has a left child, find the rightmost node of the left subtree, attach the old right subtree there, move the left subtree to the right, and step on.

Problem 2: Distribute candies

Every node holds some candies, and the tree has exactly as many candies as nodes. One move passes one candy along one edge (up or down). What is the minimum number of moves so that every node ends with exactly one candy?

Think about one edge, between a child and its parent. Look at the whole subtree under the child. It holds candies candies and has size nodes, so it has a surplus of candies - size (negative means a shortage). That surplus must cross the edge above the child, and every candy that crosses costs one move, so the edge needs exactly abs(candies - size) moves. Edges are independent, so the answer is the sum over all edges.

A postorder function returns the surplus of a subtree and adds the absolute surplus to a running total:

Python Minimum candy moves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The - 1 is the candy this node keeps. A negative return value means the subtree is short and needs candies sent down; the absolute value counts the moves either way. Time O(n).

Problem 3: Maximum difference between a node and its ancestor

Find the largest abs(a.val - b.val) over all pairs where a is an ancestor of b. Checking every ancestor of every node is O(nยทh). Instead pass two values down the tree: the minimum and maximum seen on the path from the root so far. At any node, the best difference with an ancestor is max(abs(val - low), abs(val - high)), because the extreme ancestors give the extreme differences.

When the path ends (we fall off a leaf), the spread of the path is high - low, and the answer is the biggest spread over all paths.

Python Ancestor maximum difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(h). Notice the pattern: information flows down through the parameters, and the answer flows up through the return values.

Problem 4: Nodes without a sibling

Return every value whose node is an only child. At each node, if exactly one of left and right exists, that child has no sibling. The root has no parent, so it is not counted.

Python Lonely nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The check happens at the parent, because a node cannot see its sibling by itself. This is a common beginner stumble: when a problem talks about a relationship between nodes, decide which node can see both sides.

Problem 5: Convert a BST into a min-heap

Given a BST that is also a complete binary tree, rearrange the values into a min-heap with an extra rule: a preorder walk must give the values in increasing order. (The extra rule makes the answer unique.)

The key fact: the inorder walk of a BST is the sorted order. So collect the inorder values (already sorted), then walk the tree in preorder and overwrite each node's value with the next sorted value. The tree's shape never changes, only its values. Preorder visits the parent before its children, so every parent gets a smaller value than its descendants, which is exactly the heap property.

Python BST to min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n) for the sorted list. See binary heaps for why the array layout is so convenient.

Common mistakes

  • Losing a subtree while rewiring. In flatten, save what you need (node.right) before you overwrite pointers, or use the reverse-order trick so nothing is lost.
  • Forgetting the empty tree. go(None) must return a sensible neutral value (0 surplus, no candidates).
  • Using one global low/high. Those values are per path; pass them as parameters so sibling branches do not contaminate each other.
  • Counting the root as a lonely node. Only a node with a parent can be an only child.
  • Changing the shape when converting BST to heap. Only the values move; the links stay.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the reverse-preorder flatten, why is the walk order right, left, node?

    Preorder is node, left, right. Walking the exact reverse means that when you reach a node, prev already holds its preorder successor.
  2. 2. In the candy problem, what does the function return for a subtree?

    That surplus (or shortage) must travel over the parent edge, so its absolute value is the cost of that edge.
  3. 3. What does the ancestor-difference solution pass down the tree?

    The largest difference with any ancestor is always against the smallest or the largest ancestor value, so two numbers are enough.
  4. 4. Why is the lonely-node check made at the parent?

    Binary tree nodes only point downwards. The parent is the one place where both children are visible.
  5. 5. Why does assigning sorted inorder values in preorder give a min-heap?

    Each parent receives a value earlier in the sorted sequence than any node in its subtrees, which is the min-heap property.

Summary

  • Tree problems usually pass values down (path state) and return values up (subtree results).
  • Flatten to a linked list: walk right, left, node and set node.right = prev. O(n) time, O(h) space.
  • Distribute candies: each edge costs abs(candies - size) of the subtree below it; sum in postorder.
  • Ancestor maximum difference: carry the path's min and max downward.
  • Lonely nodes: check at the parent, never at the root.
  • BST to min-heap: sorted inorder values assigned in preorder; the shape stays.

Next: more tree techniques in the tree problems lesson.