LinkedList and Trees

Linked List and Trees
element element element element
Head
Head NULL
NULL NULL
Define a node of a linked list
What does a node have?

1. Data
element 2. Reference

1. Data
element
a. What type of data? ⇒ Any
type (we will use int for
simplicity)
2. Reference
a. What type of reference?
i. What is “type” of
reference?

2. Reference
element a. What type of reference?
i. What is “type” of
reference? => Type of
reference tells what
kind of object will be
referred to by the
reference variable

2. Reference
element a. What type of reference?
i. What is “type” of reference? =>
Type of reference tells what kind
of object will be referred to by the
reference variable
ii. String s1 (s1 is a reference that
will refer to String objects)
iii. Student s1 (s1 will refer to student
object)

2. Reference
element a. What will be the type of
reference “next"?
i. Since next will refer to
a Node (the next node
in the list) thus it will be
of same type as the
node
Define a linked list
What does a linked list

have?
element 1. It only has reference to
head of the list (the
very first node)
2. It may have other
properties like number
of nodes in the list, etc.
Linked List visualizations
● Adding elements to BEGINNING OF a list when list is empty (and element is
passed to add() method)
WHEN SOMEONE CREATES A

LINKED-LIST OBJECT using the class that
we have defined. . . the head should be
NULL
Because LINKED LIST does not even
have the first node. . . .
passed to addFirst() method)
LinkedList Object
element
head = null
Node Object
Create a node with element

newNode
Element and put null in
“next” variable
Beacause newly created

NULL
node is NOT referring to any
other node . . . .
●
Make head of the list refer to element

newNode
that node. . .
LinkedList Object
head NULL
● Adding elements to BEGINNING OF a list when list is NOT empty (and
element is passed to add() method)
●
element
LinkedList Object
head
●
1 Create a node with
LinkedList Object next variable
NULL Node Object

head
2
newNode
NULL
● Make the new node refer to
1 current head of the list
(Note: head is still referring to
that node)
LinkedList Object
NULL Node Object

head
2
newNode
● Make newly created node as the
1 current head
LinkedList Object
NULL Node Object

head
2
newNode
●
The END RESULT will
newNode
Look like this. . . .
LinkedList Object
head 1
2
Newly created Node has reference to the previous head NULL

● Adding elements to LAST OF a list when list is empty (and element is
●
NULL
LinkedList Object
head
Node Object
●

newNode
“next” variable
Because newly created

NULL
node is NOT referring to any
other node . . . .
●

newNode
that node. . .
LinkedList Object
head NULL
● Adding elements to LAST OF a list when list is NOT empty (and element is
LinkedList Object
head
NULL
LinkedList Object
head
NULL
passed to add() method) [What is the end result that we expect]
element
element
element element element
LinkedList Object
head NULL
NEW NODE at the end of the list

Create a new node
With data = element
and
Next = null
element
element
LinkedList Object
head
NULL
NULL
Make the last node refer to
the newly created node
element
element
LinkedList Object
head
The question is:
How will we reach the LAST NODE? (we don’t have any direct
NULL
reference to it. . . .SO WE WILL HAVE TO USE THE head to
reach the last node
element
element
LinkedList Object
head Start with temp at head. . .

Move temp until it reaches NULL
the last node NULL
temp
element
element
LinkedList Object
head
The question is:
NULL
How will we know that it is the last node?
NULL
temp => The last node has next = null
element
element
LinkedList Object
head
NULL
NULL
temp
element
element
LinkedList Object
head
NULL
temp
● Adding elements to a certain position between (1) and (sizeOfList

+ 1) (say position = 2)
NULL
● Adding elements to a certain position between (1) and (sizeOfList

+ 1)
NULL
head
NULL
Create a new node that has the element and refers to

NULL
NULL
head
NULL
To insert it at any position “p” you have to go to

(p-1)th node that is JUST BEFORE the position you
want to insert at
NULL
temp
head
NULL
Start with temp (at head) . . .then temp must jump

(p-2) times to reach the (p-1)th node
NULL
Say p = 4 (I want to add a node at 4th position0 temp
head
NULL
After reaching the 3rd position . . .

Make newNode refer to the the next of temp
Say p = 4 (I want to add a node at 4th position0 temp
head
NULL
Then make
next of temp . .
.refer to the
new node
NULL
The final result will be. . .

NULL
NULL
● Adding elements to a list when list is empty (and element is passed to add()
method)

Element and put null in next
variable
● Adding elements to a list when list is empty (and element is passed to add()
method)

that node. . .
head
Tree Implementations (Representation of a Binary NODE)
int data
left right
Could Could
Be null or could refer to some other Be null or could refer to some other
node (which will be the left child of this node (which will be the rightchild of this
node node
Tree Implementations (Representation of a Tree)
A tree is an object that will only contain 1

reference, which is the reference to the root of the
tree
That root is of type BinaryTreeNode
When we create this tree object, the root is null

(That means the tree is EMPTY)
Tree Implementations
add(1)
1
root = null
null null
Create a new node. . . .

add(1)
root 1
null null
Make it root. . . .
Tree Implementations add(2)
root 1 2
null null null

null
Create a new node. . . .

root 1
null
2
null null
Make it left child of root. . . .

root 1 3
Create a new node. . . . null

null null
2
null null
root 1
2 3
null null
null null
Make it right child of root. . .

.
4
root 1
null null
2 3
null null
null null
Create new node. . . .

4
root 1
leftOf null null
Root
2 3
null null
null null
Make it left child of [left child of

root]. . . .
root 1
leftOf
Root
2 3
null null
4 null
Make it left child of [left child of

null root]. . . .
null
root 1
rightOfRoot
2 3
null null
4 null
null null
Tree Implementations add(6),
add(7)
2 3
4 5 6 7
DFS 2 BFS 3
4 5 6 7
1. Left after right
Inorder: Left - Root - Right
Tree Implementations Preorder: Root - Left - Right
Postorder: Left - Right - Root
DFS 2 3
4 5 6 7
1. Left after right
Inorder: Left - Root - Right
Tree Implementations Preorder: Root - Left - Right
Postorder: Left - Right - Root
1 Inorder : 4, 2, 5, 1, 6, 3, 7
Preorder : 1, 2, 4, 5, 3, 6, 7
Postorder : 4, 5 , 2, 6, 7, 3, 1
DFS 2 3
4 5 6 7
DFS Variants
Inorder : 4, 2, 5, 1, 6, 3, 7
Preorder : [1], [2, 4, 5], [3, 6, 7]
Postorder : [4, 5 , 2], [6, 7, 3],
[1]
BFS Traversal Using Queue
1
1
2 3
4 5 6 7
BFS Order:
BFS Traversal Using QUeue
1 1
2 3
4 5 6 7
BFS Order:
1 1
2 3
4 5 6 7
BFS Order: 1
1 1
2
2 3
4 5 6 7
BFS Order: 1
1 1
2 3
2 3
4 5 6 7
BFS Order: 1
1 2
3
2 3
4 5 6 7
BFS Order: 1
1 2
3
2 3
4 5 6 7
BFS Order: 1 2
1 2
3 4 5
2 3
4 5 6 7
BFS Order: 1 2
2 3
4 5 6 7
BFS Order: 1 2 3 4 5 6 7
BFS Traversal Using Recursion
1 Compute the height of the

tree = 3
2 3
4 5 6 7
BFS Order:
Compute the height of the tree = 3
1 For loop will call

printNodesAtLevel() in the following
manner :
2 3
printNodesAtLevel(root, 1, 1)
4 5 6 7 printNodesAtLevel(root, 3, 1)
Or printNodesAtLevel(root, i, 1)
BFS Order: Read: print nodes at level i starting
from root which is at level 1
Code for printNodesAtLevel()
1
level is equal to currentLevel
2 3 So the root node gets printed
4 5 6 7
BFS Order: 1
1
Level is not equal to current
2 3 level and node is not null
either . . .
So a call to
4 5 6 7 printNodesAtLevel(node(2),2, 2)
BFS Order: 1
printNodesAtLevel(node(2), 2,
1 2)
Node(2) is at the current level

2 3 . . .so it will be printed
4 5 6 7
BFS Order: 1 2
After returning from printing

1 the left child. . .
Right child will be printed . .

2 3 .in the similar manner . .
4 5 6 7
BFS Order: 1 2 3
Create a
Node
root
Make it
root
root
root
Tree Implementations : Deletion in a binary search tree
delete (12)
10
5 15
3 6 12 16
delete (12)
10
findNode(root, 12)
Will find the node that contains

the element to be deleted, i.e
node 12
5 15
3 6 12 16
delete (12)
10
The node reference is
then passed to
deleteNode()
node
5 15
deleteNode(node)
3 6 12 16
delete (12)
root
10 deleteNode(node)
Find the left and right

children of the “node”
node
5 15
left = null
right = null
node is not equal to

3 6 12 16
root
delete (12)
root
10
left = null
right = null
node
5 15 node is not equal to
root
and
It is a LEAF NODE
3 6 12 16
root delete (12)

10
currentNode
getParent(root,
node)
node
5 15 Starting from root
as the current
node,it will find
the parent of the
node object (2nd
3 6 12 16
parameter)
root delete (12)

10
currentNode getParent(root,
node)
node
5 15 Here 12 is the left
child of
currentNode. .. so
recursion will start
returning and 15
3 6 12 16
will be returned as
the parent
root delete (12)

10
parent getParent(root,
node)
node
5 15 Here 12 is the left
child of
currentNode. .. so
recursion will start
returning and 15
3 6 12 16
will be returned as
the parent
If node is the left child of
root delete (12) parent then make left child
10 as null node
parent
leftOfParent
5 15
12
rightOfParent
3 6 null 16
root delete (15)

10
5 15
3 6 null 16
root delete (16)

10
findNode(root, 15)
node
Will find the node that contains
the element to be deleted, i.e
15
5 15
3 6 null 16
root delete (15)

10 The node reference is
node then passed to
deleteNode()
5 15 deleteNode(node)
3 6 null 16
root delete (15) deleteNode(node)
10 Find the left and right children of

the “node”
node
left = null
right = Node[16]
5 15 node is not equal to root
right
3 6 null 16
root delete (15)

10
parent =
node getParent(root,node[15])
5 15
right
3 6 null 16
root delete (15)

left = null
10 right = Node[16]
parent
Here the node to be deleted
node
has only RIGHT CHILD
5 15
right
3 6 null 16
root delete (15)

left = null
10 right = Node[16]
parent
node Node is right of
parent
5 15
right
3 6 null 16
root delete (15)

10 left = null
parent right = Node[16]
node
Node is right of parent
5 15 parent.setRight(right)
right
3 6 null 16
root delete (15)

10 left = null
5 parent.setRight(right)
right
3 6 16
root delete (15)

10 left = null
right
5 16 parent.setRight(right)
3 6
Node (Assume: Not

10 the root node)
minSuccessor
5 15
3 6 12 16
Node (Assume: Not

12 the root node)
minSuccessor
12
5 15
Temp = 10 (get data from the node to
be deleted)
3 6 16
Node (Assume: Not

12 the root node)
minSuccessor
10
5 15
Temp = 10 (get data from the node to
be deleted)
3 6 16

LinkedList and Trees

Uploaded by

Copyright:

Available Formats

LinkedList and Trees

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

LinkedList and Trees

Uploaded by

Copyright:

Available Formats

Linked List and Trees

element element element element

element element element element

What does a node have?

What does a node have?

What does a node have?

What does a node have?

What does a node have?

What does a linked list

WHEN SOMEONE CREATES A

Create a node with element

Beacause newly created

Make head of the list refer to element

NULL Node Object

NULL Node Object

NULL Node Object

Newly created Node has reference to the previous head NULL

Create a node with element

Because newly created

Make head of the list refer to element

element element element element

element element element element

NEW NODE at the end of the list

head Start with temp at head. . .

● Adding elements to a certain position between (1) and (sizeOfList

● Adding elements to a certain position between (1) and (sizeOfList

Create a new node that has the element and refers to

To insert it at any position “p” you have to go to

Start with temp (at head) . . .then temp must jump

After reaching the 3rd position . . .

The final result will be. . .

Create a node with element

Make head of the list refer to element

A tree is an object that will only contain 1

That root is of type BinaryTreeNode

When we create this tree object, the root is null

Create a new node. . . .

null null null

Create a new node. . . .

Make it left child of root. . . .

Create a new node. . . . null

Make it right child of root. . .

Create new node. . . .

Make it left child of [left child of

Make it left child of [left child of

1 Compute the height of the

1 For loop will call

Node(2) is at the current level

After returning from printing

Right child will be printed . .

Will find the node that contains

Find the left and right

node is not equal to

root delete (12)

root delete (12)

root delete (12)

root delete (15)

root delete (16)

root delete (15)

root delete (15) deleteNode(node)