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

Click For Summary
The discussion focuses on creating an algorithm to determine if all leaves in an ordered tree, derived from a binary tree, are at the same depth. Participants clarify the definitions and relationships between ordered trees and binary trees, emphasizing that an ordered tree can have multiple children per node, while a binary tree cannot. The algorithm should traverse the tree to find the depth of each leaf, utilizing a pre-order traversal method. It is noted that during traversal, the depth of each leaf should be recorded and compared to ensure uniformity across all leaves. The conversation concludes with a consensus on the approach to implement the algorithm effectively.
  • #61
I like Serena said:
I'm not sure what you mean... :confused:

I meant that that what we found isn't the actual depth, but the actual depth+1..
Or am I wrong? (Thinking)
 
Technology news on Phys.org
  • #62
evinda said:
I meant that that what we found isn't the actual depth, but the actual depth+1..
Or am I wrong? (Thinking)

That's why we always need to consider if anything should be plus or minus 1! (Rofl)
 
  • #63
I like Serena said:
That's why we always need to consider if anything should be plus or minus 1! (Rofl)

(Bigsmile) (Wasntme) (Whew)

So, do we have to change something? (Thinking)
 
  • #64
evinda said:
(Bigsmile) (Wasntme) (Whew)

So, do we have to change something? (Thinking)

What is it that you think might need to be changed? (Wondering)
 
  • #65
I like Serena said:
What is it that you think might need to be changed? (Wondering)

Do we have to increment the depth, maybe, only when the child of the node we are looking at is not NULL? (Thinking)
 
  • #66
evinda said:
Do we have to increment the depth, maybe, only when the child of the node we are looking at is not NULL? (Thinking)

It seems to me that makes the algorithm unnecessarily complicated.
Better would be to initialize depth to -1 instead of 0. (Thinking)

Note that if we execute the algorithm on a non-existent (NULL) tree, it should work consistently, meaning it should find a depth of -1. (Nerd)
 

Similar threads

MHB Finding Depth of Perfect & Complete Binary Trees
  • · Replies 1 ·
Replies
1
Views
2K
MHB How Can You Check if a Binary Tree Satisfies the Properties of a 2-3 Tree?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Checking if a Binary Tree is Full: A Hint
  • · Replies 1 ·
Replies
1
Views
2K
MHB Deleting Leaf Nodes from an Ordered Binary Tree
  • · Replies 2 ·
Replies
2
Views
1K
MHB Does Max-Kruskal Algorithm Find the Maximum Spanning Tree?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Finding the $j^{th}$ Smallest Element in an AVL Tree
  • · Replies 7 ·
Replies
7
Views
2K
Having trouble with algorithm to build a function tree
  • · Replies 4 ·
Replies
4
Views
1K
MHB Divide Binary Search Tree at Key k: Algorithm & Analysis
  • · Replies 10 ·
Replies
10
Views
3K
MHB How to check if search problem has no solution in depth limit search?
  • · Replies 1 ·
Replies
1
Views
1K
C/C++ What should I be most familiar w/for C++ Data Structs & Algorithms
  • · Replies 5 ·
Replies
5
Views
2K