AI Hints
DSA in Python · Lesson 61 of 132

Trees

Branching data.

⏱ 2 min read▶ Video at 1:11:44🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Not all data fits in a line. A family tree branches. So do the folders on your computer, and the menus in an app. A tree is a data structure where each item can have children, which can have children of their own.

Trees
From the video: Trees
  • Not everything is a line
  • Family trees, folders, menus
  • Items with children

Tree words

A tree starts at the root, the node at the top. Each node can have children below it, and every node except the root has exactly one parent. Nodes with no children are called leaves. And the height of a tree is the number of levels from the root down to the deepest leaf.

Rootthe top node
Childrennodes below
Leafno children
Heightlevels to the deepest leaf

A binary tree

A binary tree is a tree where each node has at most two children, called left and right. Our tree node class holds a value and two links. A helper file builds a sample tree for us, and a picture of it. Here we print the picture, and look at a few of its parts. Run it.

binary_tree.pypython
from tree import sample, PICTURE

root = sample()
print(PICTURE)
print("root:", root.value)
print("children:", root.left.value, root.right.value)
print("a leaf:", root.left.left.value, root.left.left.left)
Output
        8
      /   \
     3     10
    / \      \
   1   6      14
      / \    /
     4   7  13
root: 8
children: 3 10
a leaf: 1 None
Also uses tree.py
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def sample():
    return TreeNode(8,
        TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
        TreeNode(10, None, TreeNode(14, TreeNode(13))))

PICTURE = '        8\n      /   \\\n     3     10\n    / \\      \\\n   1   6      14\n      / \\    /\n     4   7  13'

Summary

A tree has a root, children, and leaves. A binary tree gives each node at most a left and a right child. Next, visiting every node in a tree.

Key takeaways
  • Root, children, leaves
  • Binary: left and right
  • Height = levels
Next up: Tree Traversals — depth first