Give two binary search trees, print the numbers of both together in ascending order.
Code output:
Building first BST with values:
13 37 91 88 7 16 54
Building second BST with values:
1 40 45 14 8 22 50
printing 2 BSTs in ascending order:
1 7 8 13 14 16 22 37 40 45 50 54 88 91
Let "n" be the size of the first BST and "m" be the size of second BST.
Time complexity: O(n+m).
space complexity: O(1).
space complexity: O(1) this is wrong.
ReplyDeleteThe
Stack stk1 = new Stack();
Stack stk2 = new Stack();
are using worst case O(n + m) if the tree is not balanced at all. Best case is logn + logm space. Still this is not O(1). The only way that you can make it O(1) space is if the nodes have link to the parent - there you just got for the successors in each on of the trees.