Tree | Learn for Master

  • LeetCode Serialize and Deserialize Binary Tree (Java)

    September 2, 2016 Author: david
    No comment yet

    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 Symmetric Tree

    August 8, 2016 Author: david
    No comment yet

    Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

    For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    But the following [1,2,2,null,3,null,3] is not:

    Note:
    Bonus points if you could solve it both recursively and iteratively.

     Analysis
    This problem can be easily solved using a recursive algorithm.  We defined a method with the following signature:
     
    equal(left, right)

    then we recursively call equal(left.left, right.right) and equal(left.right, right.left). 

    The method returns false as long as only one of the two nodes is null,

    [Read More...]

  • Leetcode Invert Binary Tree

    August 7, 2016 Author: david
    No comment yet

    Invert a binary tree.

    to

    Trivia:
    This problem was inspired by this original tweet by Max Howell:

    Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

    Analysis

    This problem can be solved by using both recursion and bread first traverse or Level order traverse. 

    We first invert the left tree and right tree, then put the inverted right tree as the left child,

    [Read More...]

  • LeetCode – Binary Search Tree Iterator (Java)

    July 9, 2016 Author: david
    No comment yet

    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...]

  • Morris Traversal: Inorder Tree Traversal without recursion and without stack (Java)

    June 30, 2016 Author: david
    No comment yet
    morris inorder traverse example

    Tree traversal is often implemented using Stack or Recursion. In this case, the space complexity is O(h), where h is the height of the tree. We describe a method based on Morris Traversal for tree traversal using O(1) space. 

    The basic idea of Morris Traversal is that: For current Node Cur, we use the right most leaf of its left child to record the location of Cur.

    Suppose we start from root, after running 

    preOfRoot’s right child will point to root. Now we can traverse the left branch of the tree.

    [Read More...]