Writing an Algorithm to Check Depth of Leaves in an Ordered Tree

[evinda]

Hello! (Wave)

I want to write an algorithm, that implements an ordered tree(not necessary binary tree). It should check if all the leaves of the ordered tree (that is implemented from the binary tree) are at the same depth.

Could you give me some hints how I could do this? (Thinking)

 

[evinda]

Suppose that we have, for example, this tree:

View attachment 3548

Could you explain me how we found this binary search tree:

View attachment 3551
in order to make operations at the first tree? (Thinking)

 

[evinda]

This isn't the right corresponding binary tree, right? (Thinking)

Because, I read that at a binary search tree, each node has no more than two child nodes.

 

[I like Serena]

Hello! (Wave)

I want to write an algorithm, that implements an ordered tree(not necessary binary tree). It should check if all the leaves of the ordered tree (that is implemented from the binary tree) are at the same depth.

Could you give me some hints how I could do this? (Thinking)

Hi! (Blush)

What should the algorithm implement? (Wondering)
An ordered tree (not necessarily binary)?
Or a test whether a binary tree has all leaves at the same depth?
Or a test whether an ordered tree, that is constructed from a binary tree, has all leaves at the same depth?
Or something else?

Suppose that we have, for example, this tree:

Could you explain me how we found this binary search tree:

in order to make operations at the first tree? (Thinking)

This seems to be the wrong way around.
If we have a tree like the second one, we can convert it into the binary tree that is shown first. (Wasntme)

This isn't the right corresponding binary tree, right? (Thinking)

Because, I read that at a binary search tree, each node has no more than two child nodes.

Check. $\checkmark$

 

[evinda]

Hi! (Blush)

What should the algorithm implement? (Wondering)
An ordered tree (not necessarily binary)?
Or a test whether a binary tree has all leaves at the same depth?
Or a test whether an ordered tree, that is constructed from a binary tree, has all leaves at the same depth?
Or something else?

The algorithm should test, whether an ordered tree, that is constructed from a binary tree, has all leaves at the same depth.. (Nod) (Blush)

This seems to be the wrong way around.
If we have a tree like the second one, we can convert it into the binary tree that is shown first. (Wasntme)

A ok.. (Nod) But, could you explain me how we can do this? (Thinking)

 

[I like Serena]

The algorithm should test, whether an ordered tree, that is constructed from a binary tree, has all leaves at the same depth.. (Nod) (Blush)

Actually, it's still the wrong way around.
I only know how to construct an ordered binary tree from an ordered tree. (Doh)

A ok.. (Nod) But, could you explain me how we can do this? (Thinking)

Well, we start with an ordered tree, which is not binary, as in your example where the root has 3 children.
Then we keep the link of each node to its leftmost child, and we remove all other child links, replacing them by sibling links.
Presto! An ordered binary tree. (Whew)

 

[evinda]

Actually, it's still the wrong way around.
I only know how to construct an ordered binary tree from an ordered tree. (Doh)

Well, we start with an ordered tree, which is not binary, as in your example where the root has 3 children.
Then we keep the link of each node to its leftmost child, and we remove all other child links, replacing them by sibling links.
Presto! An ordered binary tree. (Whew)

So, does this mean that we take the root, its child is the leftmost node from the next level and the other nodes of this level are the siblings of the leftmost node and so on..? (Thinking)

Or have I understood it wrong?

 

[I like Serena]

So, does this mean that we take the root, its child is the leftmost node from the next level and the other nodes of this level are the siblings of the leftmost node and so on..? (Thinking)

Or have I understood it wrong?

That sounds right.
Those siblings become child, grandchild, and great grandchild. (Nerd)

 

[evinda]

That sounds right.
Those siblings become child, grandchild, and great grandchild. (Nerd)

Nice.. (Nerd) And how can we find the depth of the leaves? (Thinking)

 

[I like Serena]

Nice.. (Nerd) And how can we find the depth of the leaves? (Thinking)

Count the number of edges from the root to each leave? (Thinking)

 

[evinda]

Count the number of edges from the root to each leave? (Thinking)

How do we know where the leaves are, at the ordered tree? (Thinking)

 

[I like Serena]

How do we know where the leaves are, at the ordered tree? (Thinking)

If the root has any nodes connected to it, it's not a leaf, but an internal node.
The connected nodes are the children of the root, which are each at depth 1. (Thinking)

If any child has nodes connected to it other than its parent, it's not a leaf, but an internal node, and those nodes are in turn its children, which have a depth that is 1 greater. (Wasntme)

Any child that has no other nodes connected to it other than its parent, is a leaf.
It has a depth that is 1 greater than its parent. (Nerd)

 

[evinda]

So, do we conclude the following?

If the root has any nodes connected to it, it's not a leaf, but an internal node.
The connected nodes are the children of the root, which are each at depth 1. (Thinking)

The node a is not a leaf.

If any child has nodes connected to it other than its parent, it's not a leaf, but an internal node, and those nodes are in turn its children, which have a depth that is 1 greater. (Wasntme)

The node b is the only child of a.

The nodes c,e are not leaves, and also they are children of b.

Any child that has no other nodes connected to it other than its parent, is a leaf.
It has a depth that is 1 greater than its parent. (Nerd)

The only leaves are k,l,i.Or have I understood it wrong? (Worried)

 

[I like Serena]

So, do we conclude the following?

The node a is not a leaf.
The node b is the only child of a.
The nodes c,e are not leaves, and also they are children of b.
The only leaves are k,l,i.

Or have I understood it wrong? (Worried)

You have understood it right! (Nod)

 

[evinda]

You have understood it right! (Nod)

Nice... (Smile) And, do we have to traverse now the tree in pre-order/ in-order/ post-order, in order to find the leaves? (Thinking)
Or, do we have to do something else?

 

[I like Serena]

And, do we have to traverse now the tree in pre-order/ in-order/ post-order, in order to find the leaves? (Thinking)
Or, do we have to do something else?

Yes. (Nod)
Those are the most common ways to traverse a tree to do anything with it.
In your case to figure out where the leaves are and what their depth is. (Nerd)

 

[evinda]

Yes. (Nod)
Those are the most common ways to traverse a tree to do anything with it.
In your case to figure out where the leaves are and what their depth is. (Nerd)

In our case, do we have to traverse the tree in pre-order? (Thinking)

 

[I like Serena]

In our case, do we have to traverse the tree in pre-order? (Thinking)

Actually, the algorithm to traverse a tree implements all 3 forms at once.
For this problem it's not relevant which order to take. (Wasntme)

 

[evinda]

Actually, the algorithm to traverse a tree implements all 3 forms at once.
For this problem it's not relevant which order to take. (Wasntme)

When we apply all forms at once, don't we traverse three times the tree? (Worried)
Or am I wrong? (Thinking)

 

[johng1]

Assume your tree is implemented with nodes with child (youngest child) and sibling pointers. For such a tree, a node p is a leaf if and only if p.child == null.

So first find the depth of some leaf node for a non-empty tree:

depth=0;
p=root;
while (p.child != null) {
  depth=depth+1;
  p=p.child;
}

Now do a non-recursive pre-order traversal with the aid of a stack s:

push(root,0);
while (!s.isEmpty()) {
  s.pop(p,d);
  if (p.child == null && d != depth) {
    return(false);
  }
  if (p.sibling != null) {
    push(p.sibling,d);
  }
  if (p.child != null) {
    push(p.child,d+1);
  }
}
return(true);

I think it's interesting to note that the above pre-order traversal is exactly the same as a level order traversal except that a stack is used instead of a queue.

 

[I like Serena]

When we apply all forms at once, don't we traverse three times the tree? (Worried)
Or am I wrong? (Thinking)

It's one traversal that is effectively pre-order.
But we can "do something" in the order we want. (Thinking)

The algorithm is:

traverseTree(node)
    if node == NULL
        return

    Do something in pre-order

    traverseTree(node->left)

    Do something in in-order

    traverseTree(node->right)

    Do something in post-order

(Wasntme)

 

[evinda]

It's one traversal that is effectively pre-order.
But we can "do something" in the order we want. (Thinking)

The algorithm is:

traverseTree(node)
    if node == NULL
        return

    Do something in pre-order

    traverseTree(node->left)

    Do something in in-order

    traverseTree(node->right)

    Do something in post-order

(Wasntme)

I haven't understood how we can apply the three different forms of tree traversal, in order to check if all the leaves have the same depth.. (Sweating)
Could you explain it further to me?

 

[I like Serena]

I haven't understood how we can apply the three different forms of tree traversal, in order to check if all the leaves have the same depth.. (Sweating)
Could you explain it further to me?

Let's take a look at the recursive algorithm again:

traverseTree(node, depth)
  if node = NULL
    // We're in the non-existing child of a leaf here.
    // This is the place where we can do something with the depth.
    return
  for each child of node
    traverseTree(child, depth + 1)

What might we do when we are in the final case of the recursive function? (Wondering)

 

[johng1]

I think I detect some confusion on your part. Here's a tree:

Now here's the associated binary tree:

 

[evinda]

Let's take a look at the recursive algorithm again:

traverseTree(node, depth)
  if node = NULL
    // We're in the non-existing child of a leaf here.
    // This is the place where we can do something with the depth.
    return
  for each child of node
    traverseTree(child, depth + 1)

What might we do when we are in the final case of the recursive function? (Wondering)

When we have, for example, this tree:

View attachment 3594

we call the functions [m]traverseTree(a,depth), traverseTree(b,depth+1), traverseTree(e,depth+2), traverseTree(f,depth+3), traverseTree(h,depth+4), traverseTree(i,depth+5)[/m], right? But.. what do we do after the command [m] return; [/m] , that is executed at the function [m]traverseTree(i,depth+5)[/m]? (Worried)

 

[I like Serena]

When we have, for example, this tree:

we call the functions [m]traverseTree(a,depth), traverseTree(b,depth+1), traverseTree(e,depth+2), traverseTree(f,depth+3), traverseTree(h,depth+4), traverseTree(i,depth+5)[/m], right? But.. what do we do after the command [m] return; [/m] , that is executed at the function [m]traverseTree(i,depth+5)[/m]? (Worried)

Right. (Smile)

And btw, the depth is initially 0, so the initial call is actually [m]traverseTree(a, 0)[/m]. (Nerd)The first time we get to the [m]return[/m], we need to register the depth.
Every other time, we need to check if the depth is the same as the one we previously registered. (Thinking)

 

[evinda]

Right. (Smile)

And btw, the depth is initially 0, so the initial call is actually [m]traverseTree(a, 0)[/m]. (Nerd)The first time we get to the [m]return[/m], we need to register the depth.
Every other time, we need to check if the depth is the same as the one we previously registered. (Thinking)

Now, I noticed that [m] e [/m] has no children, [m]f[/m] is a sibling of [m] e [/m].
Or am I wrong? (Thinking)

 

[I like Serena]

Now, I noticed that [m] e [/m] has no children, [m]f[/m] is a sibling of [m] e [/m].
Or am I wrong? (Thinking)

No. [m]f[/m] is a child of [m]e[/m].
It's only that you've drawn them horizontally next to each other. (Mmm)

 

[evinda]

No. [m]f[/m] is a child of [m]e[/m].
It's only that you've drawn them horizontally next to each other. (Mmm)

So, do we have to initialize an other variable for the next leaf?

But.. we don't know how many there are, right? (Thinking)

 

[I like Serena]

So, do we have to initialize an other variable for the next leaf?

But.. we don't know how many there are, right? (Thinking)

I don't understand your questions. (Doh)

 

[evinda]

I don't understand your questions. (Doh)

The first time we get to the [m]return[/m], we need to register the depth.
Every other time, we need to check if the depth is the same as the one we previously registered. (Thinking)

I haven't undestood how we could do this, when we don't know how many leaves there are? (Worried)

 

[I like Serena]

I haven't undestood how we could do this, when we don't know how many leaves there are? (Worried)

For what would we need to know how many leaves there are? (Wondering)

When we traverse the tree, at some point we'll get to a leaf for the first time.
At that time, we can register its depth.
Then we continue traversing the tree.
Whenever we get to a leaf again, we'll check if its depth is the same as the one we registered before. (Thinking)

 

[evinda]

For what would we need to know how many leaves there are? (Wondering)

When we traverse the tree, at some point we'll get to a leaf for the first time.
At that time, we can register its depth.
Then we continue traversing the tree.
Whenever we get to a leaf again, we'll check if its depth is the same as the one we registered before. (Thinking)

Is it maybe like that? (Thinking)

depth=0;
traverseTree(node)
  int k;
  if node = NULL
    if (k!=depth) return failure
    return
  depth=0
  for each child of node
    depth++
    traverseTree(child)
  k=depth
  return success

Or am I wrong? (Thinking)

 

[I like Serena]

1. depth=0;
2. traverseTree(node)
3.   int k;
4.   if node = NULL
5.     if (k!=depth) return failure
6.     return
7.   depth=0
8.   for each child of node
9.     depth++
10.    traverseTree(child)
11.  k=depth
12.  return success

Isn't [m]k[/m] uninitialized when we get to line 5?
That would lead to chaos and madness. (Worried)Setting it to zero in line 7, would make it zero even if we've descended into the tree.
That can't be right! (Sweating)Line 9 is the only line where depth is incremented, and it is never decremented.
That should cause problems. (Doh)Line 11 is setting [m]k[/m], but after that it is never used... (Wasntme)

 

[evinda]

Isn't [m]k[/m] uninitialized when we get to line 5?
That would lead to chaos and madness. (Worried)Setting it to zero in line 7, would make it zero even if we've descended into the tree.
That can't be right! (Sweating)Line 9 is the only line where depth is incremented, and it is never decremented.
That should cause problems. (Doh)Line 11 is setting [m]k[/m], but after that it is never used... (Wasntme)

Do we have to use a new variable $k$ or could we also do it in an other way? (Thinking)