Scribd
Upload
25 views

Week 11 (Tree DSA)

Tree data structures are hierarchical structures with nodes connected by edges. They are used to store hierarchical data and can represent many real-world examples like family trees and file systems. A tree has a root node, internal nodes, and leaf nodes. It uses terminology like parent, child, ancestor, and descendant to describe relationships between nodes. Binary trees restrict nodes to have at most two children while binary search trees organize nodes so that all left descendants are less than the parent and all right descendants are greater. Trees can be traversed in different orders and operations like searching, insertion, and deletion are used to manipulate tree structures.

Uploaded by

umarzain2005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
25 views

Week 11 (Tree DSA)

Tree data structures are hierarchical structures with nodes connected by edges. They are used to store hierarchical data and can represent many real-world examples like family trees and file systems. A tree has a root node, internal nodes, and leaf nodes. It uses terminology like parent, child, ancestor, and descendant to describe relationships between nodes. Binary trees restrict nodes to have at most two children while binary search trees organize nodes so that all left descendants are less than the parent and all right descendants are greater. Trees can be traversed in different orders and operations like searching, insertion, and deletion are used to manipulate tree structures.

Uploaded by

umarzain2005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 26

TREE DATA

STRUCTURE
Definition:
• A non-linear/hierarchical data structure.
• Used to store collection of nodes connected by directed(or
undirected) edges.
• It is an extension to the concept of linked data structure to a
structure that may have multiple relationships among its nodes.
Examples:
• Family tree.
• Table of contents of a book.
• Class inheritance hierarchy in OOP.
• Computer file system.
• Decision trees.
Example of Computer File System:
Root directory of C drive

Documents and Settings Program Files My Music

Desktop Favorites Start Menu Adobe Microsoft Office


Tree Terminology:
• Nodes: the elements in the tree
• Edges: connections between nodes
• Root: The distinguished element that is the origin of the tree
• There is only one root node in a tree
• Empty tree has no nodes and no edges
Tree Terminology:
• Parent or predecessor: the node directly above another node in the
hierarchy
• A node can have only one parent
• Child or successor: a node directly below another node in the
hierarchy
• Siblings: nodes that have the same parent
• Ancestors of a node: forefather, early version. In law, the person from
whom an estate has been inherited.
Tree Terminology:
• Decendants: A machine/system that has developed from an earlier
version. A person who is related to you and lives after you. Eg: child,
grandchild.
• Leaf node: a node without children. Also called external node.
• Internal node: a node that is not a leaf node.
Representation:
Root

Subtrees of
the root
Tree Terminology:
edges Root

nodes
Tree Terminology:
Interior or Root
internal
nodes

Leaf
nodes
Properties of Tree:
• Depth: Depth of a node “x” is the number of ancestors or edges in
path from node(x) upto the root. In other words, the number of
edges from root to “x”.
• Heigth: Heigth of a node “x” is the number of edges in longest
downward path from x-node(to leaf).
Valid Tree:
• A tree is valid if there are :
• N-nodes in a tree
• And for that we have N-1 edges.
• Valid trees are not cyclic.
• There can not be two references at the same node.
Ancestors of 5?
5 is descendant of? 1

2 3

4 6 7 8
5

10 11 9
Depth of 1, 2, 5, 9?
Heigth of 1, 3, 8? 1
Heigth of tree?

2 3

4 6 7 8
5

10 11 9
Types of Trees:
• Based on properties, trees are classified into various categories.
• There are different kinds of trees that are used in different
scenarios.
• Simplest and most common kind of tree is a tree with the property
that any node can have at most two children. It is called Binary
Tree.
Binary Tree:
• In a binary tree, there could be maximum two children od a node.
1

2 3

4 7 8
5

10 11
9
Binary Tree Components:
• In binary tree we have three components associated with it:
• Data elements
• Pointer to left subtree
• Pointer to right subtree
• These represent a node.
Types of Binary Tree(based on structure):
• Unbalanced/Degenerate Binary Tree.
• Balanced Binary Tree.
• Full Binary Tree. ASSIGNMENT PART-03
• Complete Binary Tree.
• Perfect Binary Tree.
Binary Search Tree:
A binary search tree (BST) is a binary tree where every node in the left
subtree is less than the root, and every node in the right subtree is of a
value greater than the root. The properties of a binary search tree are
recursive: if we consider any node as a “root,” these properties will
remain true.
Searching a Node in Binary Search Tree
Inserting a Node in Binary Search Tree
Tree Traversal
A binary tree is traversed when one needs to access or display its
elements. Each method produces a different order of elements
that may be useful in scenarios when needed. There are 3
methods for traversing a binary tree:
• In-order Traversal [Left-Root-Right]
• Pre-order Traversal [Root-Left-Right]
• Post-order Traversal [Left-Right-Root]
Deleting a Node in Binary Search Tree
Unbalanced Tree: Balanced Tree:
1 1

2 3

3
4 7 8

9
Introduction to AVL Trees
Rotations in AVL Trees
Operations: Insertion, Deletion and
Search
Assignment part_04
Application of trees.

You might also like