Anshu Kumar
BAN USERShouldn't the output be [1,2] [3,4] according to your explanation?
- Anshu Kumar August 09, 2012This can be solved in O(n) only. The approach am using is, keep a separate stack of node pointers. Push on the 1st node. Keep on traversing the preorder traversal
1. if the value of stack top is more than the current node value, then make the current node left pointer of stack top.
2. if the value of stack top is less that current node value, keep popping from the stack till value of stack top is more than current node. Then make current node the right child of last popped element.
Push the current node on stack in both the cases.
It may seem like an O(n^2) algo, but we are pushing and popping every element on stack only once so this is O(n) time and space.
Please check ideone.com/VohnS for details
Did you understand the question?
- Anshu Kumar July 15, 2012This test case is working normally for me. Can you give me the exact point where this test case is failing?
- Anshu Kumar May 19, 2012
This is not working! This will find the 1st node correctly, but will not always find the 2nd node
- Anshu Kumar August 15, 2012For instance consider this
5
/ \
4 6
/ \ \
1 2 7
temp1 will point to 2, and temp2 will point to nowhere!
Check carefully!