Lecture 1: Introduction to Binary Trees

Sponsor Acknowledgment

• Relevel by An Academy
  • India’s first hiring platform
  • Job within a week
  • Register for Relevel test, schedule interview with top companies
  • Free registration
• Links provided in the description

Introduction to Binary Trees

Basics

• Binary Tree: Hierarchical data structures (unlike linear data structures like arrays, stacks, queues, linked lists)
• Hierarchy: Similar to computer folders within folders
• Binary: Each node can have at most two children
• Interview Relevance: Frequently asked in interviews

Basic Terminology

• Root: Starting point of the tree
• Child: Nodes directly connected beneath another node
  • E.g., node X is the child of node Y
• Leaf Node: Nodes without children
• Subtree: Portion of the tree under a certain node
• Ancestor: Parent, grandparent, and so on of a node
  • E.g., node A is an ancestor of node B

Types of Binary Trees

1. Full Binary Tree

• Each node has either 0 or 2 children
  • E.g., Node with 2 children is “full,” node with 1 child is not

2. Complete Binary Tree

• All levels are completely filled except possibly the last level, which must be filled from the left
  • E.g., Tree is complete if all nodes are present from left to right in the last level

3. Perfect Binary Tree

• All leaf nodes are at the same level
  • E.g., Tree where all leaf nodes are equidistant from the root

4. Balanced Binary Tree

• Height must be at maximum log(n) where n is the number of nodes
  • E.g., Tree height should not exceed log2(n) when n=8, height ≤ 3
  • Usually for efficient searching and improving time complexity

5. Degenerate Tree

• Each parent node has only one child
  • E.g., Straight line tree essentially a linked list

Conclusion

• Like & Subscribe: Support the channel for more upcoming series
• Comments: Motivation to create more content