0

Binary Tree Longest Consecutive Sequence

Problem statement:

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example:

Longest Consecutive

 

Logic:

For each node we need to check if next node has a value equal to currentNode.value+1 because as per constraint only increasing order is allowed. If yes, increment count, else for that node number of elements in sequence will be 1. Before returning function call maxLength will store maximum number of elements in sequence till now. Recursively call this function for each child of node.

Code:

 

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)