Class BinaryTree

java.lang.Object
io.openml.gearbox.algorithms.binarytree.BinaryTree
public final class BinaryTree extends Object
Binary tree gearbox that can be used practically.

(Art of Computer Programming - Volume 1, Ch. 2.3)A binary tree is an information structure recursively defined formally as a finite T of one or more nodes such that

  • there is one specially designated node called the root of the tree, root(T); and
  • the remaining nodes (excluding the root) are partitioned into m ≥ 0 disjoint sets T_1, ..., T_m and each of these sets in turn is a tree. The trees T_1, ..., T_m are called the subtrees of the root

  • Method Details

    • recoverTree

      public static <T> void recoverTree(TreeNode<T> root, Comparator<T> comparator)
      Recover a binary search tree whose 2 elements are out of order.
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the binary tree
      comparator - A strategy that defines the relative ordering of node values. For example, if node values are integers, then Comparator<Integer> comparator = Integer::compare

    • invertTree

      public static <T> TreeNode<T> invertTree(TreeNode<T> root)
      Inverts a binary tree.
      Type Parameters:
      T - The type of value store in the node
      Parameters:
      root - The root of the tree to be inverted
      Returns:
      the root of the inverted tree

    • flatten

      public static <T> MutableTreeNode<T> flatten(MutableTreeNode<T> root)
      Flattens a binary tree to a linked list.

      If the root is null, this method does nothing. For example 

          1        1
   / \        \
  2   5   =>   2
 / \   \        \
3   4   6        3
                  \
                   4
                    \
                     5
                      \
                       6
      Type Parameters:
      T - The type of value store in the node
      Parameters:
      root - the root of the binary tree
      Returns:
      the head of the flattened list

    • upsideDownBinaryTree

      public static <T> MutableTreeNode<T> upsideDownBinaryTree(MutableTreeNode<T> root)
      Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, this method flips it upside down, turns it into a tree where the original right nodes turned into left leaf nodes, and return the new root.

      For example 

          1
   / \
  2   3
 / \
4   5
      becomes 
        4
 / \
5   2
   / \
  3   1
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the original tree
      Returns:
      the root of the new tree

    • getRightMostNode

      public static <T> TreeNode<T> getRightMostNode(TreeNode<T> root)
      Returns the right most leaf of a binary tree.

      If the tree root is null, this method returns null

      Type Parameters:
      T - The type of value store in the node
      Parameters:
      root - the root of the tree
      Returns:
      the right most leaf of the binary tree.

    • findDuplicateSubtrees

      public static <T> List<TreeNode<T>> findDuplicateSubtrees(TreeNode<T> root, Function<T,String> serializer)
      Return all duplicate subtrees in a binary tree.

      For example 

          1
   / \
  2   3
 /   / \
4   2   4
   /
  4
      The duplicates are 
        2
 /         and          4
4
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the binary tree
      serializer - A strategy that generates a unique string for each node of the tree
      Returns:
      roots of all duplicates

    • generateBst

      public static List<TreeNode<Integer>> generateBst(int max)
      Returns all structurally unique binary search trees that store values 1 ... max.

      For example, given max = 3, return all 5 unique BST's shown below 

         1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
      Parameters:
      max - the max value stored in the tree
      Returns:
      all structurally unique binary search trees that store values 1 ... max

    • subtreeWithAllDeepest

      public static <T> TreeNode<T> subtreeWithAllDeepest(TreeNode<T> root)
      Returns the binary tree node with the largest depth such that it contains all the deepest nodes in its subtree.

      For example 

      
                  3
               /    \
              5      1
            /  \   /  \
          6    2  0    8
             /  \
            7   4
      This method returns the node with value 2 in the diagram, because 7 and 4 are the deepest nodes. Although nodes 5, 3 and 2 all contain the deepest nodes but node 2 is the smallest subtree among them.
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the tree
      Returns:
      the binary tree node with the largest depth such that it contains all the deepest nodes in its subtree

    • longestConsecutive

      public static <T> int longestConsecutive(TreeNode<T> root, BiPredicate<T,T> isConsecutive)
      Returns the length of the longest consecutive sequence path of a binary tree.

      For example, return 3 for 

      1
 \
  3
 / \
2   4
     \
      5
      Return 2 for 
        2
   \
    3
   /
  2
 /
1
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the binary tree
      isConsecutive - A strategy that takes 2 node value objects and determines whether the 2nd is consecutively larger than the 1st. For example, if node value is of integer type, then the strategy is simply BiPredicate<Integer, Integer> isConsecutive = (int1, int2) -> int2 == int1 + 1;
      Returns:
      the length of the longest consecutive sequence path of the binary tree

    • longestConsecutiveNodeToNode

      public static <T> int longestConsecutiveNodeToNode(TreeNode<T> root, BiPredicate<T,T> isConsecutive)
      Returns the length of the longest consecutive sequence node-to-node path of a binary tree.

      For example, return 3 from 

        2
 / \
1   3
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - the root of the binary tree
      isConsecutive - A strategy that takes 2 node value objects and determines whether the 2nd is consecutively larger than the 1st. For example, if node value is of integer type, then the strategy is simply BiPredicate<Integer, Integer> isConsecutive = (int1, int2) -> int2 == int1 + 1;
      Returns:
      the length of the longest consecutive sequence path of the binary tree

    • largestBstSubtree

      public static <T> int largestBstSubtree(TreeNode<T> root, Comparator<T> comparator)
      Returns the size of the largest BST in a binary tree.

      For example, 

         10
   / \
  5  15
 / \   \
1   8   7
      The largest BST is 
        5
 / \
1   8
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the tree
      comparator - A strategy that defines the relative ordering of node values. For example, if node values are integers, then Comparator<Integer> comparator = Integer::compare
      Returns:
      the size of the largest BST in the binary tree or 0 if root is null

    • mergeTrees

      public static <T> TreeNode<T> mergeTrees(TreeNode<T> first, TreeNode<T> second, BiFunction<T,T,T> valueAdder)
      Merges two binary trees and returns the root of the new tree.

      The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of new tree.

      Type Parameters:
      T - The type of the node value
      Parameters:
      first - The root of the first binary tree to be merged
      second - The root of the second binary tree to be merged
      valueAdder - A strategy that adds up two node values. For example, if node values are of type integer, then BiFunction<Integer, Integer, Integer> valueAdder = Integer::sum
      Returns:
      the root of the new tree which is the merge of the two trees

    • pathCondition

      public static <T> List<List<TreeNode<T>>> pathCondition(TreeNode<T> root, Predicate<List<TreeNode<T>>> condition)
      Returns all root-to-leaf paths of a binary tree where each path satisfies a given condition.
      Type Parameters:
      T - The type of the node value
      Parameters:
      root - The root of the binary tree
      condition - A strategy that determines whether the condition has been met given an ordered root-to-leaf path
      Returns:
      all root-to-leaf paths of the binary tree where each path's sum equals to the given sum.

    • checkEqualTree

      public static <T,R> boolean checkEqualTree(TreeNode<T> root, Function<TreeNode<T>, R> computeProperty)
      Returns true if it is possible to partition a binary tree to two trees such that both have the same specified property after removing exactly one edge from the original tree.

      For example, this method returns true for a binary tree with integer node values like the following 

        5
 / \
10 10
  /  \
 2   3
      if we remove the right edge between 5 and right 10 when the provided property is the sum of all nodes
      Type Parameters:
      T - The type of the node value
      R - The type of the property. The Object.equals(Object) method must be implemented on the type
      Parameters:
      root - The root of the binary tree
      computeProperty - A strategy that computes a defined property of a binary tree
      Returns:
      true if it is possible to partition a binary tree with the satisfying condition