--- # System prepended metadata title: Binary Tree Study Guide tags: [資料結構和演算法] --- # Binary Tree Study Guide :::warning [< Return to Home Page](https://hackmd.io/@siansiansu/HknJJm0W0) ::: 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](https://leetcode.com/problems/count-complete-tree-nodes/) \[[Solution](https://hackmd.io/@siansiansu/Bkr-YWzBA)\] - 🟨 [230\. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) [[Solution](https://hackmd.io/@siansiansu/r197isXMkg)] - 🟨 [285\. Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/) [[Solution]()] - 🟩 [530\. Minimum Absolute Difference in BST](https://leetcode.com/problems/minimum-absolute-difference-in-bst/) \[[Solution](https://hackmd.io/@siansiansu/SJjJRcZvR)\] - 🟩 [783\. Minimum Distance Between BST Nodes](https://leetcode.com/problems/minimum-distance-between-bst-nodes/) [[Solution](https://hackmd.io/@siansiansu/r1LL9qBG1l)] - 🟨 [1038\. Binary Search Tree to Greater Sum Tree](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/) \[[Solution](https://hackmd.io/@siansiansu/ry1wuy_8R)\] 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](https://leetcode.com/problems/binary-tree-inorder-traversal/) \[[Solution](https://hackmd.io/@siansiansu/rkLOSk9NR)\] - 🟨 [102\. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) - 🟨 [103\. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) - 🟨 [107\. Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/) - 🟨 [116\. Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/) \[[Solution](https://hackmd.io/@siansiansu/S1feVOmSR)\] - 🟨 [117\. Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/) \[[Solution](https://hackmd.io/@siansiansu/H16iBtXHR)\] - 🟩 [144\. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) \[[Solution](https://hackmd.io/@siansiansu/SyCJsx5VC)\] - 🟩 [145\. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) \[[Solution](https://hackmd.io/@siansiansu/HklUv0ec4A)\] - 🟨 [173\. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/) \[[Solution](https://hackmd.io/@siansiansu/HklH8yzHA)\] - 🟩 [637\. Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/rJr6vqmSC)\] Tree Properties and Operations ------------------------------ This section covers various properties and operations on binary trees: ### Tree Depth/Width - 🟩 [104\. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/HJq2QRwGA)\] - 🟩 [543\. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/rkdxxRvMC)\] - 🟨 [662\. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/SJWS0LczR)\] ### Tree Paths - 🟩 [257\. Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/) \[[Solution](https://hackmd.io/@siansiansu/BJwhIRqVR)\] - 🟩 [112\. Path Sum](https://leetcode.com/problems/path-sum/) \[[Solution](https://hackmd.io/@siansiansu/Skp9Ew5MA)\] - 🟨 [113\. Path Sum II](https://leetcode.com/problems/path-sum-ii/) - 🟨 [437\. Path Sum III](https://leetcode.com/problems/path-sum-iii/) - 🟥 [124\. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/) - 🟨 [129\. Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers/) \[[Solution](https://hackmd.io/@siansiansu/SykPPqpvA)\] ### Tree Structure Modification - 🟩 [226\. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/By_GArwM0)\] - 🟨 [1382\. Balance a Binary Search Tree](https://leetcode.com/problems/balance-a-binary-search-tree/) \[[Solution](https://hackmd.io/@siansiansu/H170qsY8A)\] - 🟨 [114\. Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/) ### Tree Construction - 🟨 [105\. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) \[[Solution](https://hackmd.io/@siansiansu/ByTtuM5GR)\] - 🟨 [106\. Construct Binary Tree from Inorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/) - 🟩 [108\. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) \[[Solution](https://hackmd.io/@siansiansu/S16C557rR)\] - 🟨 [889\. Construct Binary Tree from Preorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/) - 🟨 [1008\. Construct Binary Search Tree from Preorder Traversal](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/) - 🟨 [2196\. Create Binary Tree From Descriptions](https://leetcode.com/problems/create-binary-tree-from-descriptions/) \[[Solution](https://hackmd.io/@siansiansu/ByunhGGdA)\] ### Tree Validation - 🟨 [98\. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) \[[Solution](https://hackmd.io/@siansiansu/H1udzlcfC)\] - 🟨 [1361\. Validate Binary Tree Nodes](https://leetcode.com/problems/validate-binary-tree-nodes/) - 🟩 [100\. Same Tree](https://leetcode.com/problems/same-tree/) \[[Solution](https://hackmd.io/@siansiansu/rybFpoufA)\] - 🟩 [101\. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/) \[[Solution](https://hackmd.io/@siansiansu/ByXma2dMR)\] - 🟩 [110\. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/rJGobDPzA)\] - 🟩 [572\. Subtree of Another Tree](https://leetcode.com/problems/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](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/) \[[Solution](https://hackmd.io/@siansiansu/BJM2R8vz0)\] - 🟨 [236\. Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/HkpJJD5MR)\] - 🟨 [1123\. Lowest Common Ancestor of Deepest Leaves](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/) \[[Solution](https://hackmd.io/@siansiansu/B1CpljQuA)\] - 🟨 [1740\. Find Distance in a Binary Tree](https://leetcode.com/problems/find-distance-in-a-binary-tree) - 🟨 [2096\. Step-By-Step Directions From a Binary Tree Node to Another](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/) \[[Solution](https://hackmd.io/@siansiansu/H1hXjs7uC)\] ### Tree View Problems - 🟨 [199\. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/) ### Serialization and Deserialization - 🟥 [297\. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) ### Leaf Node Related - 🟩 [404\. Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/) - 🟩 [872\. Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/) ### Node Deletion - 🟨 [1110\. Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest/) \[[Solution](https://hackmd.io/@siansiansu/rkDWpRVuR)\] - 🟨 [450\. Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/) ### Tree and Linked List Combination - 🟨 [1367\. Linked List in Binary Tree](https://leetcode.com/problems/linked-list-in-binary-tree/) \[[Solution](https://hackmd.io/@siansiansu/BJTmZIY3R)\] Problem Difficulty Legend ------------------------- - 🟩 Easy - 🟨 Medium - 🟧 Medium-Hard - 🟥 Hard - ⬛ Very Hard Additional Resources -------------------- - [Binary Search Tree Visualization](https://www.cs.usfca.edu/~galles/visualization/BST.html) - [Data structures: Binary Tree (Video)](https://www.youtube.com/watch?v=H5JubkIy_p8)