• Tree - a non-empty collection of nodes & edges
• Node - can have a name and carry other associated information
• Path - a list of distinct nodes in which successive nodes are connected by edges. Any two nodes must have one and only one path between them, else it is not a tree

• Root - starting point (top) of the tree
• Parent (ancestor) of a node A - the node "above" node A
• Child (descendent) of a node A - the node "below" node A
• Siblings - nodes that have same parent
• Leaf (terminal node) - a node with no children
• Level of a node - the number of edges between this node and the root
• Depth of a node - the number of edges from the root to that node.
  The depth of the root is 0.
• Height of a node - the largest number of edges from that node to a leaf.
  The height of each leaf is zero
• Height of a tree - the longest path from the root to a leaf node.
• Balanced tree - the difference between the height of the left subtree and the right subtree is not more than 1.
• Ordered trees - The order of the children matters, i.e. children are listed in a particular order.

• Exactly one path connecting any two nodes
• A tree with N nodes has N - 1 edges

A. Java version

Class TreeNode
{
	Object  element;
	TreeNode  firstChild;
	TreeNode  nextSibling;
}

B. C++ version

struct Treenode
{
	Object  element;
	Treenode  *firstChild;
	Treenode  *nextSibling;
};

Each  node has at most two children.

Height of a well-balanced tree with N leaf-nodes : about log₂N.

1 + 2 + 22 + 23 = 24 - 1 = 15

pre_orderVisit(tree)
{ 
  
 if (current == NULL) return;	
 else
  {
     process (current);
     pre_orderVisit (left_tree);
     pre_orderVisit (right_tree);
  }
}

in_orderVisit(tree)
{ 
 if (current == NULL) return;
 else	
   {
     in_orderVisit (left_tree);
     process (current);
     in_orderVisit (right_tree);
   }
}

post_orderVisit(tree)
{ 
 if (current == NULL) return;
 else	
   {
     post_orderVisit (left_tree);
     post_orderVisit (right_tree);
     process (current);
   }
}

Class BinaryNode
{
	Object Element;		// the data in the node
	BinaryNode left;	// Left child
	BinaryNode right;	// Right child
}

struct BinaryNode
{
	Object Element;		// the data in the node
	BinaryNode *left;	// Left child
	BinaryNode *right;	// Right child
};