Katkat
Back

Solve array, tree, and maze problems

MetaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to combine binary tree traversal with spatial grouping and grid-based pathfinding to determine if nodes with specific values are reachable from a starting point in a maze.

Problem Statement

You are given a binary tree where each node contains an integer value. First, perform a 'vertical order traversal' of the tree: group nodes by their horizontal distance from the root (the root is at column 0, its left child at -1, its right at +1, etc.). Within each column, nodes should be ordered by their depth (top to bottom).

Next, represent the results of this traversal as a 2D grid. The grid has N rows and M columns, where N is the maximum depth of the tree and M is the total number of unique vertical columns identified. Each cell in the grid holds the node value if a node exists at that (depth, column) position, or 0 if the position is empty.

Finally, given a starting coordinate (start_row, start_col) and a target value target, determine if there exists a path of non-zero values starting from the coordinate to any cell containing the target value. You can only move to adjacent cells (up, down, left, right) that also contain non-zero values.

Function Signature

def can_reach_target(root, start_row, start_col, target):

Constraints

  • The tree has up to 10^4 nodes.
  • Tree node values are non-zero integers.
  • Grid dimensions are derived from tree geometry.

Example 1

Input: Tree: [1, 2, 3, 4, null, 5, 6], Start: (0, 1), Target: 5 Explanation: Root (1) is col 0, depth 0. Children (2, 3) are col -1/1, depth 1. The grid is constructed based on these columns. Check if a path of non-zeros exists from (0, 1) to a cell containing value 5.

Edge Cases

  • Tree with only a root node.
  • The target value is not present in the tree.
  • The start coordinate contains a 0 (invalid starting point).

Hints

Hint 1

Use a hash map or dictionary to group nodes by their column index, storing depth and value for each.

Hint 2

Once you have the nodes mapped by column and depth, map them into a 2D list or matrix by normalizing the column indices to be non-negative.

Hint 3

Use Breadth-First Search (BFS) or Depth-First Search (DFS) on the resulting grid to find if the target value is reachable from the starting cell through connected non-zero cells.

Follow-up questions

  • How would your approach change if you were required to find the shortest path (minimum number of steps) to the target instead of just reachability?
  • If the tree is very deep but narrow, how would you optimize the grid representation to save memory?
  • What is the time and space complexity of your solution in terms of the number of nodes `V` in the tree?