## Determine if a binary tree is height-balanced

Title: How to determine if a binary tree is height-balanced? Source: www.geeksforgeeks.org A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of “much farther” and different amounts of work to keep them balanced. Consider a height-balancing scheme where following conditions should be ...

## Rat in a Maze

Title: Rat in a Maze Source: www.geeksforgeeks.org Let us discuss Rat in a Maze as another example problem that can be solved using Backtracking. A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A ...

## Check if a binary tree is BST

Title: A program to check if a binary tree is BST or not Source: www.geeksforgeeks.org A binary search tree (BST) is a node based binary tree data structure which has the following properties. • The left subtree of a node contains only nodes with keys less than the node’s key. • The right subtree of ...

## Determine two trees are Same Tree

Title: Same Tree Source: leetcode.com Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. Python solution Python ''' https://leetcode.com/problems/same-tree/ ''' # Definition for a binary tree node. # class TreeNode(object): # ...

## Sum Root to Leaf Numbers1

Title: Sum Root to Leaf Numbers Source: leetcode.com Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example, 1 / \ 2 3 123     1   / \  2   ...

## Simplify Path

Title: Simplify Path Source: leetcode.com Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" click to show corner cases. Corner Cases: Did you consider the case where path = "/../"? In this case, you should return "/". Another corner case is the ...

Title: Reverse Linked List II Source: leetcode.com Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. Python solution Python ...

## Remove Duplicates from Sorted List II

Title: Remove Duplicates from Sorted List II Source: leetcode.com Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3. Python solution Python ''' https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ ''' # Definition for singly-linked list. # class ListNode(object): # def ...

## Range Sum Query 2D – Immutable

Title: Range Sum Query 2D – Immutable Source: leetcode.com Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) ...

## Range Sum Query – Immutable

Title: Range Sum Query – Immutable Source: leetcode.com Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 12345 Given nums = [-2, ...