Binary Tree (二叉树)

Abstract

---

• The maximum number of nodes at nth Level is 2^(n-1)

Implementation

---

Implementation with Linked List

• Linked List

Implementation with Array

• Array
• Given the index of parent node is i, the index of its left child is i*2+1, right child is i*2+2

Leetcode Questions

---

Properties

• 111. Minimum Depth of Binary Tree
• 104. Maximum Depth of Binary Tree
• 101. Symmetric Tree
• 257. Binary Tree Paths
• 404. Sum of Left Leaves
• 513. Find Bottom Left Tree Value
• 112. Path Sum

Modification & Structure

• 226. Invert Binary Tree
• 106. Construct Binary Tree from Inorder and Postorder Traversal
• 654. Maximum Binary Tree
• 617. Merge Two Binary Trees

Common Ancestor

• 236. Lowest Common Ancestor of a Binary Tree

Terminologies

---

Root Node

• Node without parent node

Leaf Node

• Node without any child nodes
• Its 2 pointers point to null

Edge

• The link created by Pointer that links up 2 nodes

Level

• Increments from the top to bottom of the Binary Tree
• Root Node is at level 1

Degree

• The number of child nodes of a particular node
• In Binary Tree, it is 0, 1, 2

Height

• The number of Edge traversed from Root Node to the furthest Leaf Node

Node Height

• The number of Edge traversed from the current node to the furthest Leaf Node

Depth

• The number of Edge traversed from Root Node to a particular node

Sidenote

In some questions or textbook, Height and Depth are defined based on the number of nodes traversed instead of Edge. In this case, we need to +1

Balance Factor

• The difference in Height between the left and right subtrees of a node
• A measure of how unbalanced the tree is at that node

Height-Balanced

• For all nodes, Balance Factor should be no greater than 1 or smaller than -1
• This means that the tree is relatively evenly distributed, and no one subtree is significantly taller than the others
• More efficient for search, insertion, and deletion operations