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

Click For Summary

Discussion Overview

The discussion revolves around writing an algorithm to check if all leaves of an ordered tree, which may not necessarily be a binary tree, are at the same depth. Participants explore various aspects of tree structures, including the conversion between ordered trees and binary trees, and the methods for determining leaf nodes and their depths.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants seek clarification on whether the algorithm should check an ordered tree or a binary tree for leaf depth consistency.
  • There is a discussion about how to construct an ordered binary tree from an ordered tree, with some participants suggesting methods for this conversion.
  • Participants propose that a node is a leaf if it has no children other than its parent, and they discuss how to identify leaves in the context of an ordered tree.
  • There are questions about the appropriate tree traversal methods (pre-order, in-order, post-order) to find leaves and their depths.
  • One participant suggests a non-recursive pre-order traversal method to check the depth of leaves in a tree implemented with child and sibling pointers.

Areas of Agreement / Disagreement

Participants express differing views on the correct interpretation of the tree structures and the algorithm's requirements. There is no consensus on the best approach to implement the algorithm or the traversal methods to use.

Contextual Notes

Participants mention various assumptions regarding tree structures and traversal methods, but these assumptions are not universally agreed upon. The discussion includes unresolved questions about the depth-checking algorithm and the specifics of tree traversal implementations.

Who May Find This Useful

This discussion may be useful for individuals interested in algorithms related to tree data structures, particularly those exploring the properties of ordered trees and binary trees.

  • #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
2K
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 How to check if search problem has no solution in depth limit search?
  • · Replies 1 ·
Replies
1
Views
1K
MHB Divide Binary Search Tree at Key k: Algorithm & Analysis
  • · Replies 10 ·
Replies
10
Views
3K
C/C++ What should I be most familiar w/for C++ Data Structs & Algorithms
  • · Replies 5 ·
Replies
5
Views
2K