0

Print singly linked list in reverse order

Problem:

Printing singly linked list is a little tricky problem because singly linked list only stores address to of the next node, no previous node address is stored in any node.

Logic:

This problem can be solved easily using recursion. Recursively call PrintReverse function till root is not null and start print.

For last node his next is null, so for that null function will return and executing line below recursive call will start execution which will start printing node values. As print line execution starts from last node, linked list will be printed in reverse order.

Implementation:

0

Reverse singly linked list

Problem:

In singly linked list, each node contains reference to next node. Address of previous node is not stored in any node, so reverse a singly linked list is a tricky question.

Logic:

For start we will assign previous node as null and currentNode as head of linked list.Till we reach to the last node of list, first store next node in a temporary node and make current node’s next as previous node. Then for next iteration, current node become previous node and nextNode becomes CurrentNode.

Implementation:

0

Sum of leaf nodes in binary tree

Problem:

Calculate sum of all the leaf nodes in binary tree.

Logic:

In this implementation we are passing 0 as initial result. When node is a leaf node(left child and right child is null) we are assigning node value to result. At the end of calls we are calculating addition of leaf nodes (that is result returned by each left and right sub-tree’s function call).

If you want to understand recursive call and how we will get correct output as result, you can refer this and try to trace this function in same way.

To calculate sum of leaf nodes , all nodes of tree are visited, so complexity of function will be O( n)

0

Find height of binary tree

Problem:

Calculate height of a binary tree:

Logic:

In binary tree left subtree and right subtree are also binary trees. We will calculate height of each subtree and will select maximum of both. 1 is added to maximum height of tree to add distance of root from a subtree. Recursive method call was made for each node till node is null to get height of a tree.

If root is null (for left and right child of leaf node) we are returning value -1 because in a final result we are adding 1 . If we return  0 instead of -1 then for leaf node we will get height as 1 (o+1) instead of 0 which is wrong. So to balance 1 we are returning -1 in if condition.

If you want to understand recursive call and how we will get correct output as result, you can refer this and try to trace above function in same way.

Also if you are new to recursion, you can check my article on recursion.

To calculate height all nodes of tree are visited, so complexity of function will be O( n)

0

Sum of all nodes in Binary tree

Problem:

Calculate sum of all nodes in a binary tree.

You refer following image to understand  function calls in above recursive method.

Sum of Nodes recursive stack trace

 

We need to visit all nodes, so time complexity will be O( n)

0

Simple Run Length Encoding.

Problem statement :

if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3de1x6″

Basically Run Length Encoding.

Easiest way to do this is using a Dictionary data structure.

You travel through the string once (O(n)) and fill the dictionary as following :

Key : Char Value: Count,

so w:4, a:3, d:1, e:1, x:6.

After filling the dictionary, you can just travel through the dictionary and concat key+value to print run length encoded string.

To preserve the order you can also use LinkedHashSet<> data structure.

here is the code using Dictionary.