2
$\begingroup$

What exactly is the top view of a binary tree?

I find great ambiguity and lack of clarity from the articles I find.

For example, this is what is used to demonstrate the top view on geeksforgeeks:

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

They go on to say that the top view is 4 2 1 3 7. The problem here is that they leave a lot of speculation on what isn't the top view. Consequently it becomes ambiguous to implement in code.

Stackoverflow examples are not any better. Hackerrank's example is even worse.

So I have signed up here hoping someone will tell me explicitly what the top view is because I have been trying to find out for 2 days. For instance, what is the top view of this tree:

      1
       \
        14
       /  \
      3    15
     / \
    2   7
       /  \
      4     13
     / \   /
    5   6 10
         /  \
        8    11
         \    \
          9    12

And if I may be bold to ask, why is it important?

$\endgroup$
1
$\begingroup$

Here is an important remark first. No, the top view of a binary tree is NOT important, however it is defined. It is just a temporary concept defined for the sake of that problem, although it might be interesting.

Now, there can be several ways to define the top view of a binary tree. There is no definitive way. That is not a problem, as long as the exercise/challenge/task define it well and unambiguously. However, this is not the case with that HackerRank problem, which does NOT define such an ambiguous concept clearly. In fact, there is no rigorous definition. The example given helps little. In fact, that problem and its online judge expects us to view a binary tree in a way that is different from my first reaction, as well as Steven's interpretation! I would blame the author of that problem, who was either inexperienced or did not pay enough attention while authoring that problem. (To be fair, he might be much more intelligent and prudent than us. Apparently not on this problem, though. Anyway, we can thank him at least for contributing to the HackerRank site, even if that problem causes more harm than progress.)

Lesson learned, again: not all resources on the internet are reliable or important.


Now let me explain what is meant by that HackerRank problem, as reverse-engineered from the expected results and the problem tester's solution.

Suppose we already have the binary tree in the form of a root, vertices and parent-childrens between the vertices. For example, root 1, vertices 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and 5.left=1, 5.right=10, 1.right=2, 10.left=6, 2.right=3, 6.right=7, 3.right=4, 7.right=8, 8.right=9. Now we put the root at some place at level 0.

           5

Now we add the children of 5, 1 and 10 on the next level below. The left child, 1, will be move one unit to the left. The right child, 10, will be moved one unit right.

           5
        /     \
      1         10

Now put 1's children and, then, 10's children on the next level. As before, the right child of 1, 2, will be put one level below and one unit right to 1. The left child of 10, 6, will be put one level below and one unit left to 10. Since that place is already occupied by 2, we just put 6 in the same place together with 2. However, 6 is considered covered, indicated by the parentheses around 6.

           5
        /     \
      1         10
        \     /
          2(6)

Now we put 2's and 6's children on the next level. Note that 7 is covered because 3 takes priority.

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)

Now we put 3's and 7's children on the next level. Note that 8 is covered.

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)
                   \
                    4(8)

Now we put 4's and 8's children on the next level. Well, since 4 does not have children, the right child of 8, 9 is not covered any more.

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)
                   \
                    4(8)
                        \
                          9

We have constructed a visual representation of the binary tree. Now we can quote the original statement from HackerRank, "top view means when you look the tree from the top, what you will see will be called the top view of the tree." The top view is 1, 5, 10, 4, 9. Other nodes are either covered, such as 8, or blocked by nodes above them, such as 2 and 3, or both, such as 6 and 7.

The top view of the tree in the question is 2, 1, 14, 15, 12.

The above illustration should be clear enough since it has explained away all unclear cases. Readers are encouraged to formulate a rigorous definition.

$\endgroup$
1
  • $\begingroup$ Thank you very much. I have understood. Asante! $\endgroup$
    – Gilboot
    Apr 23 '20 at 3:20
1
$\begingroup$

I think what they are trying to define is the following.

Given a rooted binary tree $T$, let $V(T)$ be the set of vertices of $T$. For $v \in V(G)$, let $P_v$ the unique path from the root of $T$ to $v$. We will call an edge $(u,w) \in P_v$ a left edge if $w$ is the left child of $u$, and a right edge otherwise.

Let $\ell_v$ and $r_v$ be the number of left and right edges in $P_v$, respectively, and define $\delta(v) = \ell_v - r_v = 2\ell_v - |P_v|$.

Let $h(u)$ be the depth of vertex $u$ in $T$ and define $\Delta(v) = \{ \delta_u \, : u \in V(T) \wedge h(u) < h(v) \}$. The top view of $T$ is the set $\{ v \in V(T) : \delta_v \not\in \Delta(v) \}$.

In your example the top view would be $\{1, 2, 12, 14, 15 \}$. In general, you can compute the top view in $O(|V(T)|)$ time thought a preorder DFS visit.

I have no idea why this is important, sorry.

$\endgroup$
6
  • $\begingroup$ Thanks alot, I will try to understand what your saying slowly. $\endgroup$
    – Gilboot
    Apr 22 '20 at 18:08
  • $\begingroup$ In the third paragraph. What is delta(v) for and how do you come up with the equation. I see 2lv - abs(Pv). 2lv is twice the number of left vertices but Pv is a path, its not a number so how can you subtract the two? $\endgroup$
    – Gilboot
    Apr 22 '20 at 18:11
  • $\begingroup$ $2 \ell_v$ is twice the number of left edges (not vertices). $|P_v|$ denotes the length of path $P_v$, that is, the number of edges of $P_v$. The equation follows from the fact that $r_v = |P_v| - \ell_v$, therefore $\delta_v = \ell_v - r_v = \ell_v - (|P_v| - \ell_v) = 2\ell_v - |P_v|$. Intuitively $\delta_v$ represents "how far" to the left vertex $v$ is with respect to the root of $T$ (notice that $\delta_v$ might be negative, meaning that $v$ is to the right of the root). $\endgroup$
    – Steven
    Apr 22 '20 at 18:16
  • $\begingroup$ OK. I get you. What about the backslash (\) in the discrete maths set equation. You are saying that from the vertices in the tree pick all those vertices that do X. What's X? $\endgroup$
    – Gilboot
    Apr 22 '20 at 18:30
  • $\begingroup$ The backslash is the set difference operator. I'm considering all vertices $u$ from the set $V(P) \setminus \{v\}$ $\endgroup$
    – Steven
    Apr 22 '20 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.