Given a binary tree, count the number of occurrences where there are two nodes with the same horizontal distance. To make it clearer, if we assume each node in a cell of a matrix, then count the number of occurrences when there is a collision of two nodes in the same cell. Here the count is 1 because 5 and 6 occupy the same cell in the matrix

Question

Accepted Answer

Count occurrences of two nodes with same horizontal distance in a binary tree

Traverse the tree using BFS or DFS and keep track of horizontal distance of each node
Store nodes with same horizontal distance in a hash table and increment count if collision occurs
Recursively traverse left and right subtrees with updated horizontal distance
Time complexity: O(n), Space complexity: O(n)

Top Amazon Sdet-I interview questions & answers

Popular interview questions of Sdet-I

Top HR questions asked in Amazon Sdet-I