Categories
  • Data Structures, Algorithms, Design Patterns 34
  • Programming Tips and Tricks 2
  • Aviation 1
Chau Ngo
  • Blog
  • Resume
  • Categories
  • Get all Paths of BinaryTree

    This post continues to explore tree algorithms and specifically printing all root-to-leaf paths when given a binary tree. It will showcase the iterative pre-order depth first traversal approach to solving this problem. The general idea is to represent a path using some sort of list structure and keep track of the level of the tree at each node. The level of the tree is the index of the list to modify.

    #       1
    #      / \
    #     9   8
    #    / \   \
    #   6   4   3
    #  / \     /
    # 2   7   5
    #
    # paths: [
    #    [1,9,6,2], 
    #    [1,9,6,7], 
    #    [1,9,4], 
    #    [1,8,3,5]
    # ]

    Approach

    As with all iterative tree traversal, we need a stack to store every node we visit such that we can backtrack each time we hit a null child. We will also need another stack to store every level we visit and backtrack as we encounter a null child. Lastly, we need two lists, one to store the current path we are constructing or updating, and the second list to store all the paths. As mentioned, the idea is to use the level of the current iteration as the index to modify in the path list. Once we hit a node with null children, we add the current path to the list of all paths. This process is repeated until all leaf nodes are visited.

    public static List<String> getBinaryTreePaths(TreeNode root) {
        Stack<TreeNode> parents = new Stack<TreeNode>();
        Stack<Integer> levels = new Stack<Integer>();
        List<Integer> path = new ArrayList<Integer>();
        List<String> paths = new ArrayList<String();
        TreeNode cur = root;
        Integer level = 0;
    
        while (!parents.isEmpty() || cur != null) {
            if (cur != null) {
                if (level >= path.size())
                    path.add(cur.data);
                else
                    path.set(level, cur.data);
    
                if (cur.left == null && cur.right == null)
                    paths.add(path.toString());
    
                levels.push(level++);
                parents.push(cur);
                cur = cur.left;
            }
            else {
                TreeNode parent = parents.pop();
                cur = parent.right;
                level = levels.pop() +1;
            }
        }
    
        return paths;
    }
    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Invert a Binary Tree

    Made popular by Max Howell in his 2015 Tweet, inverting a Binary Tree has became one of the must kn...

    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Fuel System

    One of the most widely known aircrafts in general aviation is the Cessna 172. Depending on the year and model, the aircraft may be equipped with one of the two ways that fu...

    Posted 1 year ago by Chau in Aviation.
  • Rabin Karp Substring Search in Java

    This post will explore one of the substring search algorithms known as Rabin-Karp created by Richard M. Karp and Michael O. Rabin. There are two concepts to talk about, the...

    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Merge Two Sorted Lists

    Write an algorithm that merges two sorted lists. The general idea to approach this problem is to have two pointers for the two lists. There will be another pointer to itera...

    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Determine if BinaryTree is Balanced

    This post will explore the problem of checking whether a binary tree is balanced or not. A binary tree is considered to be balanced if the height difference between two sub...

    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Letter is Constructible from Magazine

    The problem in this post is concerned with answering the question of whether a given letter can be reconstructed with a given magazine. The letter is reconstructible when a...

    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Palindromic Permutation

    This post explores the question of if the characters of a given word can rearranged such that the final word is a palindrome. For example, the word "edified" coul...

    Posted 1 year ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Convert Roman Numeral to Integer and Vice Versa

    This post will explore the situations where there is a need to convert a roman numeral to integer and vice versa. The common basic symbols in the roman numeral system are I...

    Posted 3 years ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Palindrome Integer

    Given an integer, determine if it is a palindrome number.

    Approaches

    There are a couple of methods in approaching this problem. The first thing that comes ...

    Posted 3 years ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Lowest Common Ancestor of Two Nodes in a Binary Tree

    Any two nodes in a binary tree has the root node as a common ancestor, assuming both nodes are in the same tree. The lower common ancestor node is the furthest node from th...

    Posted 4 years ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Singleton Design Pattern

    The singleton design pattern is classified as a creational pattern. It is appropriate for scenario where only one copy of the class is needed because singleton enforces tha...

    Posted 4 years ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Reverse an Integer

    Given an integer, compute and return its reverse form. This problem becomes a regular reversal problem if the integer is converted into a string to get its character array....

    Posted 4 years ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Abstract Factory Design Pattern

    The Abstract Factory Design Pattern is classified as a creational pattern and is similar to the Factory Design Pattern in a sense that Abstract Factory creates other factor...

    Posted 4 years ago by Chau in Data Structures, Algorithms, Design Patterns.
  • Factory Design Pattern

    The Factory Design Pattern is one of the most used design patterns. It is classified as a creational pattern under the Gang of Four (GoF). The intention behind the Factory ...

    Posted 4 years ago by Chau in Data Structures, Algorithms, Design Patterns.
← Previous