Validate Binary Search Tree | Binary Tree is BST or Not

By | | , , ,
Leave a comment

In this post, I am going to discuss a very famous interview problem validate binary search tree or in other words check if a binary tree is BST or not.

Given the root of a binary tree, We have to write a code to check if it is a binary search tree (BST) or not.

The property of a valid binary search tree (BST) is:

i) The left subtree of a node contains only nodes with keys less than the node’s key.
ii) The right subtree of a node contains only nodes with keys greater than the node’s key.
iii) Both the left and right subtrees must also be binary search trees.

For example –

→

Add Two Numbers

By | | ,
Leave a comment

Let’s discuss a problem add two numbers as lists and their java code.

Given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. We have to write a code to add these two numbers and return the sum as a linked list.

For this problem, you may assume the two numbers do not contain any leading zero, except the number 0 itself.

For example –

Linked List 1 : 2 -> 4 -> 6 -> NULL

Linked List 2 : 5 -> 6 -> 4 -> NULL

Result : 7 -> 0 -> 1 -> 1 -> NULL

Explanation :

In this example first, we added 2 and 5 the result is 7. Then, 6 and 4 the result is 10, so we put 0 and take 1 as a carry. Then, we added 6, 4, and 1 (carry) the result is 11, so we put 1 and take 1 as a carry.

→

Plus One | Add One to Number Represented as Array

By | | , ,
Leave a comment

In this problem, We have given a non-empty array which represents a non-negative integer. Write a code to add one to the number.

Each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1 –

Input:  [1, 3, 4]

Output: [1, 3, 5]

In this example, the array represents the number 134. When we add 1 to it, the new number is 135.

Example 2 –

Input : [1, 2, 9]

Output: [1, 3, 0]

The number is 129. When we add 1 to 129. The new number is 130.

Example 3 –

Input : [9, 9, 9]

Output: [1, 0, 0, 0]

For the number 999, when you add 1, the new number would be 1000. If you think in terms of array, the new array size would be the previous array size plus one.

→