Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: 1
/ \
3 4
Output: 3 4
Input: 2
/ \
4 7
/ \
8 5
Output: 8 5 7
EDGE CASE
Input: 1
Output: 1
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Trees, some things we should consider are:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Pre-Order Traversal of the Tree. At every node, verify if the node is a leaf or not. If so, print the value and continue.
1) Basecase: If the current node is Null, return
2) Recursive: Get all nodes with no children
a) If the current node has no children, print its value
b) Recurse Left and Recurse Right
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def print_leaf_nodes(self, root: TreeNode) -> None:
# Basecase: If the current node is Null, return
if not root:
return
# If the current node has no children, print its value
if not root.left and not root.right:
print(root.val, end = " ")
# Recurse Left and Recurse Right
self.print_leaf_nodes(root.left)
self.print_leaf_nodes(root.right)
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in the in the binary tree. H
represents the height of the binary tree
O(N)
because we will need to access each node in the binary tree.O(H)
because we only need space to hold the recursive stack, which is dependent on the height of the binary tree.