Binary Tree Terms, TreeNode and Level-Order Input
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A tree is a way to store data that branches, such as folders on a disk or an organisation chart. This lesson names the parts of a binary tree, writes the TreeNode class and reads the level-order format that coding tests use.
Nodes, links and the words for them
Binary tree is a structure of nodes with one root, where every node has at most two children: a left child and a right child. A node with no children is a leaf. Each node except the root has exactly one parent.
A tree keeps data in nodes joined by links, like an organisation chart. The top node is the root. In a binary tree every node has at most two children, called left and right.
The TreeNode class
TreeNode is an object that stores one value and two references, left and right, to its child nodes. A reference that is None means the child is missing.
Each node becomes one small object. It holds a value and two references, left and right. None means there is no child on that side.
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))print(root.val, root.left.val, root.right.right.val)print(root.left.left.left, root.right.left)Example 1 · Is this node a leaf?
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
def is_leaf(node): return node.left is None and node.right is None
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))print(is_leaf(root))print(is_leaf(root.left))print(is_leaf(root.left.left))False False True
What this code does
- A leaf has no left child and no right child. Compare with
is None, because a value such as 0 is also false. - Node 4 is a leaf, so the last line prints True.
root.left.left is the left child of the left child. A leaf has None on both sides, so asking for .val of a missing child would fail with an error.
Level-order input
Level-order input lists a tree's values row by row, from the root down and from left to right, with null for every missing child. A missing node has no children listed after it.
Tests give a tree as a list read row by row, top to bottom and left to right. The word null marks a missing child, and the children of a missing node are not listed.
tokens = "1 2 3 4 5 null 6".split()values = [None if t == "null" else int(t) for t in tokens]print(values)print("root", values[0], "children", values[1], values[2])print("children of 2:", values[3], values[4])print("children of 3:", values[5], values[6])Example 2 · Which items are the children?
tokens = "1 2 3 null null 4 5".split()kids = iter(tokens[1:])for token in tokens: if token != "null": print(token, "->", next(kids, "null"), next(kids, "null"))1 -> 2 3 2 -> null null 3 -> 4 5 4 -> null null 5 -> null null
What this code does
- Each non-null item takes the next two items. Nodes 2, 4 and 5 are leaves, so they get null and null.
- The two
nullitems after 3 belong to node 2, because 2 comes first in level order.
Node 3 has no left child, so null stands in its place. Every non-null node takes the next two items in the list as its children.
Build the tree from the list
Make one node for every non-null item. Then walk the nodes in order and give each real node the next two items as its left and right child. An iterator hands out the items one by one.
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = rightdef build(tokens): nodes = [None if t == "null" else TreeNode(int(t)) for t in tokens] kids = iter(nodes[1:]) for node in nodes: if node: node.left, node.right = next(kids, None), next(kids, None) return nodes[0]root = build("1 2 3 4 5 null 6".split())print(root.right.right.val, root.right.left)Example 3 · A tree that leans to one side
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
def build(tokens): nodes = [None if t == "null" else TreeNode(int(t)) for t in tokens] kids = iter(nodes[1:]) for node in nodes: if node: node.left, node.right = next(kids, None), next(kids, None) return nodes[0]
root = build("7 null 9 null 12".split())print(root.left, root.right.val, root.right.left, root.right.right.val)None 9 None 12
What this code does
- The
nullafter 7 is its missing left child. Then 9 is the right child, and 9 has no left child and a right child 12. - Every missing child needs its own
null, but nothing is written below it.
Example 4 · Build with a queue
from collections import deque
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
def build_queue(tokens): if tokens[0] == "null": return None values = iter(tokens) root = TreeNode(int(next(values))) queue = deque([root]) while queue: node = queue.popleft() left, right = next(values, "null"), next(values, "null") if left != "null": node.left = TreeNode(int(left)) queue.append(node.left) if right != "null": node.right = TreeNode(int(right)) queue.append(node.right) return root
root = build_queue("1 2 3 4 5 null 6".split())print(root.left.right.val, root.right.right.val)5 6
What this code does
- The queue holds nodes that still wait for children. This is the version many interview books show.
- It gives the same tree as the shorter builder. Use the shorter one when writing quickly, and know this one for interviews.
Example 5 · Count the nodes
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
def build(tokens): nodes = [None if t == "null" else TreeNode(int(t)) for t in tokens] kids = iter(nodes[1:]) for node in nodes: if node: node.left, node.right = next(kids, None), next(kids, None) return nodes[0]
def count(node): if node is None: return 0 return 1 + count(node.left) + count(node.right)
root = build("1 2 3 4 5 null 6".split())print(count(root), count(None))6 0
What this code does
- A missing child counts as zero nodes. Any other node counts itself plus both sides.
- This is the first recursive function on a tree. The next lesson uses the same shape for traversals.
next(kids, None) returns None when the list has run out, so a leaf at the end of the input needs no special case. The cost is O(n) time and O(n) space.
Next step
Check your understanding
10 quick questions