Abstract
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 asi * 2 + 1
, the index of its right child is calculated asi * 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 complexity for search, insertion and deletion
Poor performance!
Binary tree should deliver 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