Trees

Question 1

What is Breadth First traversal?

Answer 1

Breadth-First traverses each level before moving onto next levels

Question 2

What is Depth First traversal?

Answer 2

Depth First makes its way to the bottom level first and works back up

Question 3

What is the programmatic difference between Breadth-First and Depth First?

Answer 3

• Node children are added to the end of the array in Breadth First
• Node children are added to the beginning of the array in Depth First

Question 4

If you are asked a traversal question regarding width, what traversal method would you use?

Answer 4

A Breadth-First method

Question 5

What is the difference between a Binary Tree and a Binary Search Tree?

Answer 5

A Binary Search Tree requires the left node to be less than the parent and the right node to be more.

Question 6

How do you find the min or max in a BST?

Answer 6

To find the min, while node.left, set node to node.left, then return the node.val

Question 7

What are the 4 steps in a function to find the lowest common ancestor of 2 nodes in a BST?

Answer 7

• Write a function that takes a root, and 2 nodes as args.
• Then recursively call that function on root.right and root.left.
• If left and right are not null, return the root
• Otherwise return either left or right