In binary trees, are sibling nodes necessarily ordered?

0
votes

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

1
data-structurestreebinary-tree
Condition (1) applies to all binary trees. Condition (2) applies only to binary search trees. The examples from g2g are binary trees, but not binary search trees. Or maybe condition (2) is just oddly defined. In a binary tree, there is a left child position and a right child position. You could consider that to be an ordering in an of itself. - Matt Timmermans
meta.stackexchange.com/questions/75491/… - Shridhar R Kulkarni

1 Answers

1
votes

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.