Tree and Graph

0 views - 1 minute readEdit this post

I rely on your support to keep this website running. If you find the content valuable, please consider making a small donation. whether it’s ₹25/$1 or ₹500/$5.

Donate

Secured by Stripe

Topics which are not mentioned in post: Conversion of General Tree to Binary Tree & Binary Tree Traversal: PreOrder, InOrder and PostOrder.

Non-linear data Structure — Tree, Graph

Tree

  • Is hierarchical structure with root node, siblings, nodes, parent nodes, etc.
  • Nodes are connected with edges/branches from parents to children.
  • A node can one have one parent
  • Operations on tree,
    • Traversal
    • Sorting
    • Searching
    • Insertion
    • Deletion
    • etc.

Untitled

Graph

  • Graph is non linear data structure which is collection of nodes and edges.
  • Nodes are connected with edges.
  • A node can be connected back to itself through other nodes.

Untitled

Basic Terms

General Tree -

  • A tree where each node has most two child nodes.

Forest -

  • Collection of multiple trees

Level Numbers -

  • The level or depth of a node form the root with the root at level 0

degree -

  • The number of sub trees or child nodes.

in-degree -

  • Number of incoming edges to node.

out-degree -

  • Number of outgoing edges from a node.

root node -

  • Top level node forming entire tree.

leaf node -

  • A tree with no children node.

directed edges -

  • a edge with defined direction from one node to another.

path -

  • sequence of nodes connected by edges that allow traversing the graph.

depth -

  • number of edges from the root node to last specified node
  • similar as level.

Application of binary tree

BST -

  • Used Binary trees are used for efficient searching and retrieval of data, especially when the data is sorted.

File system -

  • Binary trees are used to organize files and directories in a hierarchical file system structure.

Decision Trees -

  • Binary trees can also used for decision tree which helps to manage decision making process.

Sorting -

  • binary tree are used to implement sorting algorithm to order items.

Search engines -

  • Binary trees are used in search engines to organize and index web pages.

Priority queues -

  • Binary trees can be implemented as priority queues which are data structures that allow elements to be prioritized and retrieved in specific order.

Did you enjoyed the post?

Twitter (x)