Binary Trees

Question 1

104. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Answer 1

1. Create base case, which is when it hits a leaf node, where root node is None and make that return 0
2. Return 1 plus the max of the function call on the left and right node

Basically leaf node will return 1 + max(0,0) and will make its way up the stack/recursion

Question 2

100. Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Answer 2

1. Base case where both p and q are null, they are equal, so return True
2. Case where p or q is null, they are not equal so return False
3. Case where p.val and q.val is not equal, they are not equal so return False
4. Last case, is calling on child nodes. So call isSameTree on both the left and right nodes and compare their bool value with “and”
   
   • if True and True, True
   • If True and False, False
   • If False and False, False

Question 3

226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Answer 3

1. Check case where root is none. if so, just return null root
2. create variables left and right, where they traverse down the left and right trees respectively using recursion
3. swap the left and right by setting the root.left to right and root.right to left variables.
4. return the root

Question 4

105. Construct Binary Tree from Preorder and Inorder Traversal

Answer 4

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Question 5

572. Subtree of Another Tree

Answer 5

https://leetcode.com/problems/subtree-of-another-tree/

Question 6

102. Binary Tree Level Order Traversal

Answer 6

https://leetcode.com/problems/binary-tree-level-order-traversal/

Question 7

98. Validate Binary Search Tree

Answer 7

https://leetcode.com/problems/validate-binary-search-tree/

Question 8

230. Kth Smallest Element in a BST

Answer 8

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Question 9

235. Lowest Common Ancestor of a Binary Search Tree

Answer 9

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Question 10

211. Design Add and Search Words Data Structure

Answer 10

https://leetcode.com/problems/design-add-and-search-words-data-structure/

Question 11

208. Implement Trie (Prefix Tree)

Answer 11

https://leetcode.com/problems/implement-trie-prefix-tree/