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. It implements the following Functions:
  • TreeNode implements Linked Tree Node
    • TreeNode Constructor
    • Retrieve the Tree Node Value
    • Retrieve the Left Tree Node
    • Retrieve the Right Tree Node
  • DiameterHeightPair implements Diameter Height Duo
    • DiameterHeightPair Constructor
    • Retrieve the Height
    • Retrieve the Diameter
  • Retrieve the Right-side View of the Tree
  • Generate the DiameterHeightPair Instance from the Root
  • 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
  • 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

Module Computational Core Module
Library Computation Support
Project Environment, Product/Definition Containers, and Scenario/State Manipulation APIs
Package Assorted Data Structures Support Utilities

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 rootNode)
    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 Tree
      Returns:
      The Right-side View of the Tree

    • TreeDiameter

      public static final TreeUtil.DiameterHeightPair TreeDiameter​(TreeUtil.TreeNode rootNode)
      Generate the DiameterHeightPair Instance from the Root
      Parameters:
      rootNode - 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