Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/246217369943433216
edited tags
Link
Kaveh
Kaveh
  • 22.7k
  • 4
  • 53
  • 113
English
Source Link
Gilles 'SO- stop being evil'
Gilles 'SO- stop being evil'
  • 44.2k
  • 8
  • 120
  • 185

Binary Two definitions of balanced binary trees - Properties

who can give me a solution to my doubt. It is concerning about BINARY TREES:

The theorem says:

Def 1: A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

Def 2: A binary tree is balanced if for anyI have seen two leaves the differencedefinitions of the depth is at most 1balanced binary trees, which look different to me.

  1. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

  2. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

My doubt is the following: ifDoes every tree that statisfy Defsatisfies def. 1 also statisfy Defsatisfy def. 2? is that true? And this is valid also inWhat about the other way round?

Thanks for helping me!

Binary trees - Properties

who can give me a solution to my doubt. It is concerning about BINARY TREES:

The theorem says:

Def 1: A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

Def 2: A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

My doubt is the following: if every tree that statisfy Def. 1 also statisfy Def. 2? is that true? And this is valid also in the other way round?

Thanks for helping me!

Two definitions of balanced binary trees

I have seen two definitions of balanced binary trees, which look different to me.

  1. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

  2. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

Does every tree that satisfies def. 1 also satisfy def. 2? What about the other way round?

Source Link
forrestGump
forrestGump
  • 787
  • 1
  • 10
  • 14

Binary trees - Properties

who can give me a solution to my doubt. It is concerning about BINARY TREES:

The theorem says:

Def 1: A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

Def 2: A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

My doubt is the following: if every tree that statisfy Def. 1 also statisfy Def. 2? is that true? And this is valid also in the other way round?

Thanks for helping me!