2

Given a binary tree I need to implement a method findAllElements(k) to find all the elements in the tree with a key equal to k.

The idea I had is the first time you come across an element with key k. All the elements with the same key should be either in the left child's right subtree or the right child's left subtree. But I was told this may not be the case?

I just need to find a way to implement an algorithm. So pseudo code is needed.

I probably should have added this sorry. But the implementation is that the left subtree contains keys less than or equal to the key at the root and the right subtree contains keys greater than or equal to the key at the root.

nbonbon
  • 1,660
  • 3
  • 18
  • 27
  • You need an algorithm but you don't understand how your tree looks like? – SomeWittyUsername Feb 28 '13 at 18:53
  • What makes you think I don't understand what my tree looks like? – nbonbon Mar 01 '13 at 20:01
  • Well, if you understand it, you wouldn't have written "*I was told this may not be the case*", and your edit to the post only enforces this assumption – SomeWittyUsername Mar 01 '13 at 21:26
  • At the time it was a question (hence the question mark) because I believed that it was the case. And if you look at the answer I provided below that does, indeed, happen to be the case. My teacher seemed to have misunderstood what I had stated. – nbonbon Mar 01 '13 at 22:40

3 Answers3

1

It depends on your tree implementation, by binary tree I assume you mean binary search tree, and you use operator< to compare the key. That is, The left subtree of a node contains only nodes with keys less(<) than the node's key, and the right subtree of a node contains only nodes with keys not less(!<) than the node's key.

e.g.

  7 
 / \
4   7
   / \
  6   8

If there is multi equal keys in the tree, do this

k < current_node_key,  search left subtree
k > current_node_key,  search right subtree
k == current_node_key, record current node , then search right tree
lostyzd
  • 4,515
  • 3
  • 19
  • 33
0

Look at the current node. If its key is higher than k, search the left subtree. If it is lower, search the right subtree. If it is equal, search both left and right subtrees (and also include the current node in the results).

Do that recursively starting from the root node.

Alex D
  • 29,755
  • 7
  • 80
  • 126
  • Bad advice. Assuming it's not just a binary tree but a **binary search tree** (not sure OP understands the difference), storage of duplicates must be well defined and it's either in left or in right subtree - it's proprietary definition of the specific BST implementation – SomeWittyUsername Feb 28 '13 at 19:00
  • He didn't say it was a "binary search tree", but just a "binary tree". – Alex D Feb 28 '13 at 19:17
  • If it's just a "binary tree", your answer is plain wrong since there is no property associated with key for a generic binary tree – SomeWittyUsername Feb 28 '13 at 19:21
  • 2
    @icepack, I feel you may be getting stuck on a certain definition of what a "binary tree" is, when in fact there are all kinds of variations on the same idea, which people still refer to as "binary trees". And there *are* some such structures which allow duplicate keys, and where duplicates can appear on *either* side. Think about this: some types of 2-ary tree structures automatically rebalance as nodes are added. Often, it is guaranteed that a certain level of balance will be maintained at all times. If duplicate keys are allowed, this implies they *must* appear on both sides at times. – Alex D Mar 01 '13 at 05:42
  • Just noticed the OP added a sentence to his question. It confirms that in the tree he is working with, equal keys *can* appear on either left *or* right. – Alex D Mar 01 '13 at 05:54
  • @AlexD You're way way off. Binary tree is a well defined term. Binary search tree along with its multiple variations (AVL, red-black etc.) is a specialization of the generic binary tree. Generic binary tree is a tree with at most 2 child nodes, there are no keys or any other properties. – SomeWittyUsername Mar 01 '13 at 07:59
0

Thought I'd come back and explain what the result should have been after conversing with me teacher. So if you perform a method findElement(k) that will find an element with the key equal to k, the element it find should be the element highest in the tree with key k (let's denote this element V).

Then from this element V, other elements the contain a key=k will either be in the left child subtree (particularly all the way to the right) or the right child subtree (particularly all the way to the left). So for the left child keep going to the next nodes right child until an element with key=k is found...now... every element in the subtree with this node as its root must have a key=k (this is the part i didn't recognize at first) thus ANY kind of traversal of this full subtree can be done to find and store all the elements in this subtree (visiting every node in it). This type of thing must be repeated for the right child but visiting every left child until an element with a key=k is found. then the subtree with this element as its root has all the other elements with key=k in it and they can be found by one again fully traversing this subtree.

That is just a word description of it obviously, sorry for the length, and any confusion. Hopefully this will help anyone else trying to solve a similar problem.

nbonbon
  • 1,660
  • 3
  • 18
  • 27