search

trekhleb / javascript-algorithms

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
MIT License
185.03k stars 29.84k forks source link

BinaryTreeNode.js height() gives one less than tree's height. #1072

Open gyaneshwar-sunkara opened 9 months ago

gyaneshwar-sunkara commented 9 months ago

The height of the tree is the number of edges in the tree from the root to the deepest node.

height right now gives one less than the total number of the edges, small tweek made will fix it.

johndub27 commented 9 months ago

You have the definition of “height” of a tree confused with the “depth” of a tree. Depth is from root to deepest node and height is from the deepest node to the root. For clarification, see:Introduction to Algorithms, 4th ed Cormen et al p.1173Thanks,JohnOn Sep 7, 2023, at 10:00 PM, Gyaneshwar Sunkara @.***> wrote:The height of the tree is the number of edges in the tree from the root to the deepest node. height right now gives one less than the total number of the edges, small tweek made will fix it.

You can view, comment on, or merge this pull request online at:   https://github.com/trekhleb/javascript-algorithms/pull/1072

Commit Summary

6800c9a BinaryTreeNode.js height() gives one less than tree's height.

File Changes (1 file)

M
src/data-structures/tree/BinaryTreeNode.js
(6)

Patch Links:

https://github.com/trekhleb/javascript-algorithms/pull/1072.patch https://github.com/trekhleb/javascript-algorithms/pull/1072.diff

—Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: @.***>

lazarljubenovic commented 9 months ago

His fix has nothing to do with height vs depth, but with the way you define an empty tree: -1 or 0. Both definitions are fine; the only important thing is to be explicit on what it actually means.