Coconote
AI notes
AI voice & video notes
Export note
Try for free
Introduction to Binary Trees
Jul 10, 2024
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
📄
Full transcript