Tree Basics

DSA · Trees

Theory

A tree is a hierarchical structure of nodes connected by edges, with one root node and no cycles. Each node can have children; nodes without children are leaves. Key terms are parent, child, sibling, depth (distance from the root), height (longest path down to a leaf) and subtree. Any tree with n nodes has exactly n-1 edges.

Why we use it

Many real things are hierarchical: folders, organisation charts, HTML documents, categories. Trees also give O(log n) searching when balanced.

When to use it

Use trees for hierarchies, sorted data with fast insert/search (BSTs), prefix lookups (tries), priority queues (heaps), and decision making.

How it works

  1. Root node
  2. Each node has children (0 or more)
  3. Nodes without children are leaves
  4. Depth = edges from root; height = longest path down
  5. A connected acyclic hierarchy

Syntax

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

Root: no parent   Leaf: no children
Height(leaf) = 0  Height(node) = 1 + max(child heights)

Example

class TreeNode:
    def __init__(self, name):
        self.name = name
        self.children = []

def show(node, depth=0):
    print("  " * depth + "- " + node.name)
    for c in node.children:
        show(c, depth + 1)

def height(node):
    if not node.children:
        return 0
    return 1 + max(height(c) for c in node.children)

root = TreeNode("CEO")
cto, cfo = TreeNode("CTO"), TreeNode("CFO")
root.children = [cto, cfo]
cto.children = [TreeNode("Data Lead"), TreeNode("Dev Lead")]
cto.children[0].children = [TreeNode("Analyst")]
show(root)
print("Height:", height(root))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic