Trees

Question 1

226. Invert Binary Tree (Easy)

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

Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Answer 1

Recursive problem solved using DFS

1. Check for empty tree, if (!root) return null. AKA base case.
2. Set root.left to a temp variable and do a switcheroo with root.left = root.right then root.right=temp
3. Call invertTree recursively with both root.left and root.right.
4. Return root.

This function works recursively to invert the binary tree in a depth-first manner. At each step, it swaps the left and right children of the current node, and then recursively performs the same operation on the left and right subtrees of the current node. This process continues until the base case is reached (i.e., when the current node is null). Finally, the root node of the inverted binary tree is returned.

Question 2

104. Maximum Depth of Binary Tree (Easy)

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.

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3

Answer 2

Use recursion with an inner function.

1. Set maxDepth to 0 outside of an inner function to create a closure.
2. In the inner function take in the node and the currentDepth. Check to see if there’s still a node (base case). If there isn’t (end of tree reached), then set maxDepth to Math.max(maxDepth, currentDepth) and return
3. If there isn’t, recursively call the function on both node.left, and node.right, incrementing currentDepth by 1.
4. Call the function, return maxDepth.

Question 3

100. Same Tree (Easy)

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.

Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false

Hint: What are two things are you testing for each iteration of the recursive loop?

Answer 3

Use binary search to check every node

Every iteration, you’re testing for two things: if p and/or q is null, or if their value is not equal

1. If p & q are null, we’ve reached the end of the tree so we can return true
2. if only one is null which you can test with (!p || !q || p.val !== q.val) because we’ve already accounted for both null, then return false
3. the only pairs that will make it through these checks are 2 equal values
4. recursively call the function for both left and right values

Question 4

235. Lowest Common Ancestor of a Binary Search Tree (Medium)

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Answer 4

iterate through the tree and FIND THE SPLIT (where p is on one branch and q is on another)

once you find the split, current has to be the lowest common ancestor

this works even if p and q are the ancestor since it doesn’t check for >= or <=

Question 5

572. Subtree of Another Tree (Easy)

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Answer 5

sameTree helper function
create a helper function sameTree that recursively goes through two trees and compares values

edge cases
check for edge cases (either root or subroot is null

call whole function recursively
recursively call isSubtree for both root.left and root.right