Binary Tree

DSA · Trees

Theory

A binary tree is a tree in which every node has at most two children, called left and right. Special shapes include full trees (every node has 0 or 2 children), complete trees (every level filled except possibly the last, filled left to right) and perfect trees (all levels full). A complete binary tree can be stored in an array, which is how heaps are implemented.

Why we use it

The two-child structure keeps algorithms simple and is the basis for binary search trees, heaps and expression trees.

When to use it

Use binary trees for BSTs, heaps, expression parsing, Huffman coding and many interview problems.

How it works

  1. Root
  2. Each node has at most 2 children: left and right
  3. Node is None? Yes: Stop (empty subtree). No: Process node, then left and right.
  4. Done

Syntax

class Node:
    def __init__(self, v): self.val = v; self.left = None; self.right = None

Array form (complete tree): children of i at 2i+1 and 2i+2, parent at (i-1)//2

Example

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

def count_nodes(n):
    return 0 if n is None else 1 + count_nodes(n.left) + count_nodes(n.right)

def max_depth(n):
    return 0 if n is None else 1 + max(max_depth(n.left), max_depth(n.right))

def tree_sum(n):
    return 0 if n is None else n.val + tree_sum(n.left) + tree_sum(n.right)

print("Nodes:", count_nodes(root), "| Depth:", max_depth(root), "| Sum:", tree_sum(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