What is an ordered tree?

explain
tree

#1

The Wikipedia link provided in the problem is quite difficult to understand from.

https://www.codechef.com/JULY17/problems/EXPTREE

Can someone please explain to me in a simple language what ordered tree exactly is?


#2

An ordered tree contains nodes (elements) which can be ordered according to a specific criteria. Often it is a binary tree, i.e. nodes have at most two children (conveniently called the left and right child). The tree is ordered when at every node, all elements in its left child tree are smaller than elements in its right subtree (and if the non-leaf node itself contains an element, it is greater than the elements in the left subtree and less than the elements in the right subtree).

(provided all elements in the tree are unique - if not, then some “greater than” / “less than” above becomes “greater or equal to” / “less or equal to”.)

Simple example:

    4
  /   \
 2     6
/ \   / \
1 3   5 7

#3

You can find better explanation here and why it is relevant to the question ->
http://cs.lmu.edu/~ray/notes/orderedtrees/


#4

http://people.cs.ksu.edu/~schmidt/300s05/Lectures/Week8.html
It will help you.


#5

I think you’ll better understand by viewing this image;-> ( http://i.imgur.com/9Gv0tdL.png )


#6

How is that relevent to the problem where values are not even there and only the arrangement of nodes are to be considered?


#7

@sudip_95 everyone has access to stackoverflow so if you are pasting answer from there atleast give credits to the original writer


#8

Thanks, exactly what I was looking for.


#9

Exactly

Lets give him Credit