Tree

A tree is a set of nodes and edges that connects the nodes. Between there could be exactly one path.

Rooted Tree

When a node is distingushed as root the thre is a rooted tree. In such a tree every node has a parent except the root node. From any node to the path of root parent is the first node in that path.

Definations

Leaf node
Siblings
Ancestors
Descendents
Length of path
Depth of node
Height of node
Height of tree
Subtree

Binary tree

Tree traversal

Preorder traversal

Postorder traversal

Inorder traversal for binary tree

Level order traversal

 

Expression tree

Prefix expression

Postfix expression

 

Infix expression

[incomplete] Complete binary tree can not have a right child without a left child.