Package org.drip.service.common

Class TreeUtil

java.lang.Object
org.drip.service.common.TreeUtil
public class TreeUtil
extends java.lang.Object
TreeUtil implements Tree Utility Functions.



Author:
Lakshmi Krishnamurthy

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static class  TreeUtil.DiameterHeightPair
    DiameterHeightPair implements Diameter Height Duo.
    class  TreeUtil.TreeNode
    TreeNode implements Linked Tree Node.

  • Constructor Summary

    Constructors
    Constructor Description
    TreeUtil()  

  • Method Summary

    Modifier and Type Method Description
    static int MinimumEditsForAverage​(TreeUtil.TreeNode node)
    Given a binary tree, return the minimum number of edits to make the value of each node equal to the average of its direct children's.
    static java.util.List<java.lang.Double> RightSideView​(TreeUtil.TreeNode root)
    Retrieve the Right-side View of the Tree
    static TreeUtil.DiameterHeightPair TreeDiameter​(TreeUtil.TreeNode root)
    Generate the DiameterHeightPair Instance from the Root
    static boolean ValidateIsStrictBST​(TreeUtil.TreeNode node)
    Given the root of a binary tree, determine if it is a valid binary search tree (BST).

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • TreeUtil

      public TreeUtil()

  • Method Details

    • RightSideView

      public static final java.util.List<java.lang.Double> RightSideView​(TreeUtil.TreeNode root)
      Retrieve the Right-side View of the Tree
      Parameters:
      root - Root of the Trtee
      Returns:
      The Right-side View of the Tree

    • TreeDiameter

      public static final TreeUtil.DiameterHeightPair TreeDiameter​(TreeUtil.TreeNode root)
      Generate the DiameterHeightPair Instance from the Root
      Parameters:
      root - The Root Node
      Returns:
      The DiameterHeightPair Instance from the Root

    • MinimumEditsForAverage

      public static final int MinimumEditsForAverage​(TreeUtil.TreeNode node)
      Given a binary tree, return the minimum number of edits to make the value of each node equal to the average of its direct children's. Note that you can only update the value of each tree node, and changing the tree structure is not allowed.
      Parameters:
      node - The Root Node
      Returns:
      Minimum Edits for the "Average" Tree

    • ValidateIsStrictBST

      public static final boolean ValidateIsStrictBST​(TreeUtil.TreeNode node)
      Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.
      Parameters:
      node - Current Node
      Returns:
      TRUE - Node represents a Strict BST