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

### 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...