CODEWITHSUNDEEP
algorithmdata-structurestree
DoReMi
DoReMi

Reputation: 221

Find all nodes near the middle of the tree

I got this question from my friend's interview: Given a binary tree, print the array of nodes(at most two nodes) from all levels that near the middle of the tree. Here is an example:

    1
   / \
  2   3 
 / \   \
4   5   9
       /
      10
The output is [ [2,3], [5,9], [10] ].
I can only think of an inefficient method: level order the tree, for each level, put all nodes in current level into an array, if the node is NULL, put a flag(maybe -1 or sth else) into the slot. At the end, print out all nodes in the middle of each array.
For the above example, my code will first get 4 arrays:
[1], [2,3], [4,5,-1,9],[-1,-1,10,-1], after this process, print out all middle values in the array which is not -1.
I believe there must exist better solutions, can anybody provide? Thanks!

Upvotes: 0

Views: 579

Answers (3)

Don Bosco
Don Bosco

Reputation: 121

We can never be sure if an element exists in an ith level until we've traversed all the elements of the tree. Hence, the time complexity can never be optimised better than O(n), which is the same as the algorithm proposed by you.

The only problem in your solution is that for each level a seperate array is required to be maintained. Though asymptotically the space complexity remains the same, in absolute numbers it becomes extra usage.

What you can do is the following:

  1. Do level order traversal.
  2. For each element when you're pushing it to the queue (for level order traversal), also maintain the deviation of the element from the middle. The root will be having deviation as 0. The root's left child will be having -1. whereas the right child will be +1.
  3. For each level, you'll need to keep a "global" element(s) on how close an element is to the middle. For a given level, there can be at max 2 elements only.
  4. Continue this for every level.

This algorithm works better space complexity wise for sparse trees.

Hope this helps!

Upvotes: 0

Yaofei Feng
Yaofei Feng

Reputation: 26

Go in-order traversal the tree and also keep the node's level

Node: 4-2-5-1-3-10-9

Level: 2-1-2-0-1-3-2

Now for the level output, we start from level 0, find left side first occurrence of 1 -- the corresponding number is 2, find the right side first occurrence of 1 -- the corresponding number is 3, so the level 1 output is <2,3>

do the same thing for level 2 output is <5,9>

for level 3 output is just<10>

Time complexity O(n) Space complexity O(n)

Same as level order traversal solution

Upvotes: 1

Pham Trung
Pham Trung

Reputation: 11284

The only way I can think of for this question is, from the root, we can divide the nodes into two type : left side of the root and right side of the root. And for each level, for the left side nodes, we find the right most node, and for the right side, we find the left most node. Hope this will help you!

Upvotes: 1

Related Questions