DSA - Trees

Data Structures and Algorithms

Introduction to Trees

Introduction to Trees

What to Expect?

Thanks

What are Trees?

Basic Terminologies

Examples

Sections

Tree Traversal

Programming Trees

01

What are trees?

A brief introduction

Definition of trees

NOT A PLANT!!

A tree represents a hierarchical nature of a structure in agraphical form. It consists of elements or nodes, with each node linked to its successors. A Tree is a non-linear data structure and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

Definition of Trees

+INFO

Why is tree considered a non-linear data structure?

Why is tree considered a non-linear data structure

It is a hierarchical structure as elements in a Tree are arranged in multiple levels. The topmost node in the Tree data structure is known as a root node. Each node contains some data, and data can be of any type.

The data in a tree are not stored in a sequential manner i.e, they are not stored linearly. Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For this reason, the tree is considered to be a non-linear data structure.

+INFO

02

Basic Terminologies

Essentials

01

02

03

Root Node

Parent Node

Child Node

Basic Terminologies

The topmost node of a tree or the node which does not have any parent node is called the root node.

The node which is a predecessor of a node is called the parent node of that node.

The node which is the immediate successor of a node is called the child node of that node.

04

05

06

Leaf Node

Ancestor

Descendant

Basic Terminologies

The nodes which do not have any child nodes are called leaf nodes.

Any predecessor nodes on the path of the root to that node are called Ancestors of that node

The node which is the immediate successor of a node is called the child node of that node.

07

08

09

Sibling

Internal Node

Node Level

Basic Terminologies

Children of the same parent node are called siblings.

The count of edges on the path from the root node to that node.

The node which is the immediate successor of a node is called the child node of that node.

10

11

12

Subtree

Degree

Depth

Basic Terminologies

Any node of the tree along with its descendant.

The depth of the tree is its highest level.

The degree is the number of child nodes in a subtree.

Basic Terminologies

03

Tree Traversal

Exploring Trees

What is Tree Traversal?

Exploring the trees

Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree. Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.

Tree Traversal

01

02

03

In-Order

Pre-Order

Post-Order

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.

Tree Traversal

04

Programming Trees

Trees In Action

Jtree, DefaultMutableTreeNode & Different Methods

The Java class, DefaultMutableTreeNode, is used to represent a general-purpose node in a tree data structure. It is included in the javax.swing.tree package.

Jtree, DefaultMutableTreeNode & Different Methods

The next slide will display the various Java methods used in trees.

The Jtree is a Java Swing component that displays a set of hierarchical data as an outline. It is included in the javax.swing package.

+INFO

Java Methods

Java Methods

05

Sample Codes

Trees In Action

Sample Codes

1. To create an empty tree:

JTree tree = new JTree();

2. To create a node:

DefaultMutableTreeNode root = new DefaultMutableTreeNode("B");

3. To create a tree with identified root node:

JTree tree = new JTree(root);

4. To add a child node

root.add(n1); //n1 is another node

Sample Codes

5. To display the children of a node:

//Convert the Enumeration type to List List childNodes = Collections.list(root.children()); System.out.print(childNodes); //or simply System.out.print(Collections.list(root.children()));

6. To display a traversed tree:

//Convert the Enumeration type to List List preTree = Collections.list(root.preorderEnumeration()); System.out.print(preTree);

Sample Codes

THANK YOU!