Trees and recursion 0/36

Lesson 1 of 5

Binary trees

Walk a binary tree in four orders and return values from children to answer questions about the whole tree.

5,594 words · 25 min read

Part 1 of 10 Binary trees

Binary trees

A linked list is a chain: each node holds a value and a link to the next node. In a binary tree each node holds a value and links to at most two nodes below it, its left child and its right child. In this lesson a tree is the input, and we write functions that answer questions about it, such as how tall it is or how far apart its two farthest nodes are.

A binary tree with six nodes. The dashed region is the subtree of 3.

In this tree:

  • The node at the top, 8, is the root. Every other node has one parent, the node directly above it.
  • A node has two children, one child or none. It matters which side a child is on: 10 has only a right child, 14, and if 14 were the left child of 10, this would be a different tree.
  • A node with no children is a leaf: 1, 6 and 14 here.
  • The subtree of a node is the node together with all the nodes below it. The subtree of 3 is 3, 1 and 6.
  • The root is on level 0, its children on level 1 and their children on level 2.
  • The height of a tree is the number of nodes on the longest path from the root down to a leaf, 3 for this tree.

A subtree is a binary tree in its own right. So a binary tree is a root with up to two smaller binary trees below it, its left subtree and its right subtree. Most functions in this lesson follow that structure: they do a little work at one node and call themselves on its two subtrees.

A binary tree in code

In code, a node is an object with three fields: its value val, and the links left and right to its children. A missing child is None.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left     # a TreeNode, or None for a missing child
        self.right = right

A problem statement cannot show linked objects, so LeetCode writes a tree as a list: the values level by level, each level from left to right, with null where a child is missing. Our tree is [8,3,10,1,6,null,14]:

The list split into levels 0, 1 and 2. The null is the missing left child of 10.

The list writes nothing below a null, because a missing node has no children. In [1,null,2,3] the root 1 has no left child, written null, and its right child is 2. The next level can only hold the children of 2, so 3 is the left child of 2. A null at the end of a list is left off, which is why the missing right child of 2 is not written.