Binary Tree

Abstract

---

• Each node has $0$ to $2$ Edge
• The maximum number of nodes at the nth level is 2^(n-1), counting from $1$

Implementation with Linked List

Refer to Linked List to understand its properties.

Binary Tree Array Representation

---

• Given the index of a parent node i, the index of its left child is calculated as i * 2 + 1, the index of its right child is calculated as i * 2 + 2. We can find the index of its parent node with (i - 1) / 2

Binary Tree Linked List Representation

---

• Compared to the array representation, the linked list representation of a binary tree is easier to scale in terms of size, but it comes with higher memory usage due to the overhead of storing pointers for each node. Additionally, it cannot take advantage of CPU cache locality as effectively as the array representation

Degenerate Binary Tree

---

• A Binary Tree in which each parent node has only one child node associated with it. Such a tree behaves like a Linked List, resulting in $O(n)$ complexity for search, insertion and deletion

Poor performance!

Binary tree should deliver $O(logn)$ in the ideal situation.

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