Binary Tree Study Guide

< Return to Home Page

Tree Types

Binary trees come in several variations, each with unique properties:

1. Complete Binary Tree (CBT): Every level is filled, except possibly the last, which is filled from left to right.
2. Perfect Binary Tree (PBT): All interior nodes have two children, and all leaf nodes are at the same level.
3. Full Binary Tree (FBT): Every node has either 0 or 2 children.
4. Binary Search Tree (BST): For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater.

• 🟨 222. Count Complete Tree Nodes [Solution]
• 🟨 230. Kth Smallest Element in a BST [Solution]
• 🟨 285. Inorder Successor in BST [Solution]
• 🟩 530. Minimum Absolute Difference in BST [Solution]
• 🟩 783. Minimum Distance Between BST Nodes [Solution]
• 🟨 1038. Binary Search Tree to Greater Sum Tree [Solution]

Tree Traversal

Understanding different traversal methods is crucial for working with binary trees:

1. Inorder Traversal: Left subtree, Root, Right subtree
2. Preorder Traversal: Root, Left subtree, Right subtree
3. Postorder Traversal: Left subtree, Right subtree, Root
4. Level Order Traversal: Visit nodes level by level, from left to right

• 🟩 94. Binary Tree Inorder Traversal [Solution]
• 🟨 102. Binary Tree Level Order Traversal
• 🟨 103. Binary Tree Zigzag Level Order Traversal
• 🟨 107. Binary Tree Level Order Traversal II
• 🟨 116. Populating Next Right Pointers in Each Node [Solution]
• 🟨 117. Populating Next Right Pointers in Each Node II [Solution]
• 🟩 144. Binary Tree Preorder Traversal [Solution]
• 🟩 145. Binary Tree Postorder Traversal [Solution]
• 🟨 173. Binary Search Tree Iterator [Solution]
• 🟩 637. Average of Levels in Binary Tree [Solution]

Tree Properties and Operations

This section covers various properties and operations on binary trees:

Tree Depth/Width

• 🟩 104. Maximum Depth of Binary Tree [Solution]
• 🟩 543. Diameter of Binary Tree [Solution]
• 🟨 662. Maximum Width of Binary Tree [Solution]

Tree Paths

• 🟩 257. Binary Tree Paths [Solution]
• 🟩 112. Path Sum [Solution]
• 🟨 113. Path Sum II
• 🟨 437. Path Sum III
• 🟥 124. Binary Tree Maximum Path Sum
• 🟨 129. Sum Root to Leaf Numbers [Solution]

Tree Structure Modification

• 🟩 226. Invert Binary Tree [Solution]
• 🟨 1382. Balance a Binary Search Tree [Solution]
• 🟨 114. Flatten Binary Tree to Linked List

Tree Construction

• 🟨 105. Construct Binary Tree from Preorder and Inorder Traversal [Solution]
• 🟨 106. Construct Binary Tree from Inorder and Postorder Traversal
• 🟩 108. Convert Sorted Array to Binary Search Tree [Solution]
• 🟨 889. Construct Binary Tree from Preorder and Postorder Traversal
• 🟨 1008. Construct Binary Search Tree from Preorder Traversal
• 🟨 2196. Create Binary Tree From Descriptions [Solution]

Tree Validation

• 🟨 98. Validate Binary Search Tree [Solution]
• 🟨 1361. Validate Binary Tree Nodes
• 🟩 100. Same Tree [Solution]
• 🟩 101. Symmetric Tree [Solution]
• 🟩 110. Balanced Binary Tree [Solution]
• 🟩 572. Subtree of Another Tree

Special Problems

This section covers unique problem types related to binary trees:

Lowest Common Ancestor

• 🟨 235. Lowest Common Ancestor of a Binary Search Tree [Solution]
• 🟨 236. Lowest Common Ancestor of a Binary Tree [Solution]
• 🟨 1123. Lowest Common Ancestor of Deepest Leaves [Solution]
• 🟨 1740. Find Distance in a Binary Tree
• 🟨 2096. Step-By-Step Directions From a Binary Tree Node to Another [Solution]

Tree View Problems

• 🟨 199. Binary Tree Right Side View

Serialization and Deserialization

• 🟥 297. Serialize and Deserialize Binary Tree

Leaf Node Related

• 🟩 404. Sum of Left Leaves
• 🟩 872. Leaf-Similar Trees

Node Deletion

• 🟨 1110. Delete Nodes And Return Forest [Solution]
• 🟨 450. Delete Node in a BST

Tree and Linked List Combination

• 🟨 1367. Linked List in Binary Tree [Solution]

Problem Difficulty Legend

• 🟩 Easy
• 🟨 Medium
• 🟧 Medium-Hard
• 🟥 Hard
• ⬛ Very Hard

Additional Resources

• Binary Search Tree Visualization
• Data structures: Binary Tree (Video)