Binary Tree

Abstract

---

• Each node has $0$ to $2$ Edge
• The maximum number of nodes at nth Level is 2^(n-1)

Implementation with Linked List

Refer to Linked List to understand its properties.

Implementation with 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. Refer to Array to understand its properties.

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