CODEWITHSUNDEEP
c++tree
이승철
이승철

Reputation: 37

find the unique elements in the binary tree

I would like to find a maximum number of unique elements in path. (path is from root to leaf).

for example, my tree is as below.

     3
    / \
   1   2
  /\    \
 1  3    5

Above tree, the answer will be 3. because there are three paths as below.

3-1-1
3-1-3
3-2-5.

and the unique elements of each path is as below.

3-1
3-1
3-2-5.

therefore the answer is 3.

My idea of how to get the number is as follows. Firstly, I found all the paths from root to leaf. and when the pointer reached the leaf node, I printed the paths and calculated the unique elements. and iterated this procedure until all nodes were visited.

Upvotes: 1

Views: 1279

Answers (1)

Nelfeal
Nelfeal

Reputation: 13269

You can build a second similarly shaped tree that holds the number of unique elements in each subpath (from the root to any node, root and leaves included). That tree can be built from root to leaves like so : the root value is always 1 since the path from root to root contains one unique element, and the value of any other node is either its parent's value or one more.

Exemple with your tree :

    3             1
   / \           / \
  1   2    =>   2   2
 / \   \       / \   \
1   3   5     2   2   3

The value of each leaf is the number of unique elements from the root to that leaf.

Although you could keep it for subsequent uses, you do not actually need to build the tree. You only need to perform a depth-first traversal while keeping track of the unique elements in the current subpath in a data structure, let's say a vector. Since you want the maximum number of unique elements, you need to keep track of the size of that vector when you hit a leaf.

The data structure can be something else than a vector, but it depends on what your elements are. You can probably use an ordered set, which would be equivalent to keeping a vector sorted. If you can hash your elements, you can use a "hashset" (std::unordered_set in C++11). If your elements are simple integers and their values are all within a relatively small range, you can use a vector of booleans instead of a hashset : initially, the vector holds N booleans to false, N being the size of the range your integers are in. Instead of adding and deleting elements, you toggle booleans at the corresponding indices.

Upvotes: 1

Related Questions