Tree data structure

Tree Data Structure

Tree

Tree is a non-linear data structure [arrays, linked lists, stacks, and queues are linear data structure] made up of nodes and edges that are directed. Here the direction is from parent to children.

A tree can be empty with no nodes or a tree may consists of root node and zero or one or more sub-trees.

Tree has the following properties;

• Only one node is the root node (root does not have an incoming edge/link).

• Every other node is connected by a directed edge from exactly one other node. The node connected by a directed edge is the child node and the node where the link comes from is the parent node.

• Every node can have any number of children.

• If a node B has a path from node A, then A is called ancestor and B is called descendant.

• Nodes without any children is called leaf node (external node).

• Nodes with at least one child is called internal node.

• Set of nodes that have edges coming in from same node are called siblings.

• The number of edges from the root to a node is called the depth of the node.

• The number of edges from the root node to the deepest leaf node is the height of the tree.

• A set of nodes and edges that are connecting a node with its descendants is called as the path. The length of a path is 1 less than the number of nodes on that path.

• The number of children that a node has is called as degree of that node.

• A node B of a tree with all of its descendants is called as sub-tree with B as its root node.

 ***************

Go to Data structures main page

tree data structure

properties of tree data structure

terminologies used in defining tree data structure

terms you need to know about tree data structure

what is tree in data structure

definition of tree

important terminologies in tree data structure