CareerCup

This might not be efficient solution.

1. Insert the first node into the queue.
2. When inserting the child nodes of the first node check whether the element is in the queue.
if(present)
a. Insert left/right child of the node which is duplicate
else
Just traverse the tree

This solution does not ensure that duplicates are removed. We need to maintain a set of seen values throughout the traversal process. A hashtable comes to mind but it might be an overkill. If the set of values is finite like letters , we could use an array.

how can both left and right children of the deleted node be linked to its parent? if all duplicated nodes are either leaves or have only one child, then the problem is relatively easier.

Otherwise, I think we need to build a new tree from scratch. Traverse the old tree and keep inserting nodes into the new tree as long as they are not a duplicate. Duplicates can be checked by a hash map on node values.

we can create a queue of linklist in which we store the data value and pointer of tree while traversing the tree by any method, like preorder or inorder. then, while inserting new node we can check in queue whether this data value is already present in queue or not. if yeas, call delete(node *H) function, which delete the node.

we can create a queue of linklist in which we store the data value and pointer of tree while traversing the tree by any method, like preorder or inorder. then, while inserting new node we can check in queue whether this data value is already present in queue or not. if yeas, call delete(node *H) function, which delete the node.

Traversal the tree level by level using queue

begin with root
1) check if left child equal to current item
1.1) if yes, delete left child and goto 1)
1.2) if no, push left child into the queue
2) same with right child
3) queue empty?
3.1) yes - exit, job is done
3.2) no - get net item from queue and goto 1)

instead of hash tables, etc. build a new binary tree with duplicates removed (check at insert) It looks like there is no structure to the keys of the binary tree node, so it shouldn't matter.

we can traverse the tree in BFS manner. and simultaneously maintain an array of keys (of binary tree). for every key we can check if it is there in array we can retain it , otherwise we can delete the key.

space complexity : o(n) for array & o(n) for queue used(as in BFS)
time complexity : o(n2) : as for each key we have to check in array whether it is presnt or not.


correct me if i m wrong..
and suggest for better solution.

Wht if there are 2 child of a duplicate node.

Just a stupid query
Why cant we use hash table?
We can have a hash table of alphabets
We can traverse the tree in BFS or DFS and put all the alphabets as they come in the hash table. If a duplicate appears it we can delete it.
Now complexity will be O(N) for traversing the tree and for each node Hash table will take O(1) time. So overall complexity we get is O(N)

Please correct me if m wrng

not add them to begin with:-)