Tree Basics

The Idea

A tree stores values in nodes that fan out downward. One node is the root; every other node has exactly one parent, and nodes with no children are leaves. Links only point down, so a tree has no cycles and no way back up.

Real-World Example

Nested folders on a disk. One folder sits at the top, every folder below it lives inside exactly one parent, and files are the dead ends. How deep something is buried is simply how many folders you had to open to reach it.

The Code

class Node:
    def __init__(self, v, kids=None): self.val, self.kids = v, kids or []

root = Node("home", [Node("docs", [Node("cv.pdf")]), Node("photos")])

def depth(node, d=0):                  # longest link count below this node
    return d if not node.kids else max(depth(k, d + 1) for k in node.kids)

print(root.val)                        # home  -> the root
print([k.val for k in root.kids])      # ['docs', 'photos']
print(root.kids[1].kids == [])         # True  -> photos is a leaf
print(depth(root))                     # 2     -> edges to the deepest file

class Node:
  def __init__(self, v, kids=None): self.val, self.kids = v, kids or []

t = Node(1, [Node(2), Node(3, [Node(4)])])
print(len(t.kids), t.kids[1].kids[0].val)