CODEWITHSUNDEEP
data-structurestreebinary-tree
diagoot
diagoot

Reputation: 59

In binary trees, are sibling nodes necessarily ordered?

Just been learning about binary trees in school, and two rules of binary trees is that

  1. every node has at most 2 child nodes
  2. there exists linear ordering defined for the children of each node (ordered pair)

Now, all types of binary trees (full, complete, etc.) are binary trees so they must satisfy these 2 conditions.

However, I saw on GeeksForGeeks this example:

enter image description here

How is 'linear ordering', ordered pair, defined here?

It seems that for the sibling nodes in this picture, some left ones are larger than the right one, some right nodes are larger than the left one.

If asked to check if a given tree is a binary tree, how do I make sure of the second property, that the children of each node have to be ordered?

Thanks

Upvotes: 0

Views: 293

Answers (1)

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

This is one of the complicated ways to introduce a binary tree.

two rules of binary trees is that

  1. every node has at most 2 child nodes
  2. there exists linear ordering defined for the children of each node (ordered pair)

Simple ways of introducing binary trees I could think of are "at most two children and no cycles" or "at most two children and unique path between any pair of vertices".

But fine. You bring up the point of linear order. Lets discuss that.

Here

A linear ordering on a finite collection of objects may be described as follows: each object has exactly one immediate predecessor object and one immediate successor object with two exceptions: A first object has no predecessor and a last object has no successor.

If you have learnt about traversal so far, with the above definition, I would take binary tree traversals as linear order - preorder, postorder, inorder, level order. This applies to all types of binary trees (full, complete, etc.) which includes the complete binary tree you posted as an image.

Upvotes: 1

Related Questions