More

    TREE DATA STRUCTURE – BASIC TERMINOLOGIES AND CONCEPTS

    A tree is a data structure used to represent hierarchical structures. A file system is an example of a hierarchical structure, where one folder can have subfolders, they can again have sub folders and so on. A tree is a non-linear data structure.

    BASIC TERMINOLOGIES

    Node

    A node is an element of the tree. A node in a tree can have any number of children.

    Root

    A root is a node without any parent element. There can be only one root node in a tree.

    Edge

    An edge is a link between two nodes.

    Leaf

    A node without any children is called a leaf node.

    Siblings

    Children of same parent are called siblings.

    Ancestor

    All nodes that come in the path between root and itself are called ancestors.

    Descendants

    All children, their children and so on which can be reached from a node are called descendants of a node. Size of a node is the number of all descendants including it.

    Depth

    Depth of a node is the length of path from root to that node.

    Depth of a tree is the depth of the node with maximum depth.

    Height

    Height of a node is the length of path from a node to the deepest descendant node which can be reached from that node.

    Height of a tree is the maximum height among all nodes in a tree.

    Level

    Set of all nodes at a given depth is called a level. For instance, root is at level 0 and all its immediate children are at level 1.

    Skew trees

    Every node except leaf node has only one child. 

    Left skew tree

    Every node except root has only one left child.  

    Right skew tree 

    Every node except root has only one right child.  

    Trie

    • An n-ary tree where characters are stored at each node.
    • Each path down the tree may represent a word.

    TREE OPERATIONS

    Balancing a Tree

    • The depth of subtree will not vary by more than a certain amount.
    • Does not mean that left and right sub trees are exactly same size.

    REFERENCES: 

    http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox