Scribd
Upload
2 views9 pages

Trees Data Structure - After DFS

A tree is a hierarchical data structure made of nodes and edges, used to represent relationships and structures like file systems and organizational charts. Key characteristics include nodes, edges, root, leaf, parent, and child, with types such as binary trees and binary search trees allowing for efficient data operations. Traversal methods like DFS and BFS are used to navigate trees, with specific orders for pre-order, in-order, and post-order traversals.

Uploaded by

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

Trees Data Structure - After DFS

A tree is a hierarchical data structure made of nodes and edges, used to represent relationships and structures like file systems and organizational charts. Key characteristics include nodes, edges, root, leaf, parent, and child, with types such as binary trees and binary search trees allowing for efficient data operations. Traversal methods like DFS and BFS are used to navigate trees, with specific orders for pre-order, in-order, and post-order traversals.

Uploaded by

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

What is a Tree?

A tree is a hierarchical data structure composed of nodes and edges. The primary
purpose of a tree is to represent relationships and hierarchical structures like file
systems, organizational charts or parsing expressions.

Key characteristics of Trees:

• Nodes: A tree consists of nodes (the data points or vertices)


• Edges: The connection between the nodes (often visualized as lines between
them)
• Root: The topmost node for which all other nodes are connected.
• Leaf: A node that has no children (its at the bottom of the tree)
• Parent: A node that has children.
• Child: A node that is a descendant of another node.

Note: Some types of trees, like binary search trees allow for fast searching, insertion
and deletion.

Depth: The depth of a node is the number of edges from the root to that node. (When
you want depth, count above the node)

Height: The height of a node is the longest path from that node to a leaf node. (When
you want height, count below the node. Always aim for longer)

Types of Trees:

• Basic Trees
o Binary Tree: A Binary tree is a tree where each node can have at most 2
children.

o Binary Search Tree:


▪ All the nodes in the left sub tree of a node should have values less
than the node’s value.
▪ All the nodes in the right sub tree of a node should have values
greater than the node's value.

This Property allows for efficient searching and insertion. Searching for a
value can be done in O (log n) time.

Basic Implementation in Python:


Binary Tree: It is a tree where each node will have at most two children. The children are
generally referred as leftChild and rightChild.

DFS(Depth-first-search) and BFS(Breadth-first-search) are two concepts which are


mostly used in graphs. But they do take some minor part in trees.

DFS => Pre-order, In-order, Post-order traversals

BFS => Level-order traversal.

First, we will look at the DFS traversals. All these will reach the depth first.

Pre => Root → Left → Right

In => Left → Root → Right

Post => Left → Right → Root.

This is the simple way to remember. Always remember the root node is tied to the name.
And a basic thumb rule is that Right always comes after Left.

All these traversals can be implemented using recursive method as well as Iteration
(using Stack). We will see both the implementations below.

Tree diagram for our practice


Pre-Order using Recursion :

Output :
Pre Order using Iteration :

Output :
In-Order recursive:

Output :
Inorder Iterative :

Output :
Post-order Recursive :

Output :
Post-order Iterative:

Output :

You might also like