• Best articles to explain Binary Indexed Trees

    Binary Indexed Trees (Fenwick Tree)

    from: http://algorithmsandme.in/2015/02/binary-indexed-trees/

    Why Binary Indexed Tree?

    Consider an array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, you have to find the sum of a range say (1,5). One way of doing this can be by keeping the sum of elements from index 0 to index i, where 0 <= i<= n. So the array with all the cumulative sum is “sum” :{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136} and to calculate sum from 1 to 5 we can simply do sum[5] – sum[1].

    [Read More...]
  • LeetCode Serialize and Deserialize Binary Tree (Java)

    Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

    Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

    For example, you may serialize the following tree

    as “[1,2,3,null,null,4,5]”,

    [Read More...]
  • Leetcode Path Sum

    Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

    For example:
    Given the below binary tree and sum = 22,

    return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

    Java Solution


    [Read More...]
  • LeetCode – Binary Search Tree Iterator (Java)

    Binary Search Tree Iterator

    • Difficulty: Medium

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

    Calling next() will return the next smallest number in the BST.

    Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

    Source: https://leetcode.com/problems/binary-search-tree-iterator/

    In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree. 

    [Read More...]
  • Leetcode – Graph valid tree solution based on Union find set

    Graph Valid Tree
    Given n nodes labeled from 0 to n – 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

    For example:

    Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

    Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.


    Given n = 5 and edges = [[0, 1], [1, 2],

    [Read More...]