Skip to content

Instantly share code, notes, and snippets.

@tonymontaro

tonymontaro/algoexperts-flattenBinaryTree.java

Last active April 16, 2020 11:15
Show Gist options
  • Save tonymontaro/0a53e781cdb2b9a038ec679d2bc0762b to your computer and use it in GitHub Desktop.
Save tonymontaro/0a53e781cdb2b9a038ec679d2bc0762b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tonymontaro revised this gist Apr 16, 2020. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion algoexperts-flattenBinaryTree.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    class Program {
    public static BinaryTree flattenBinaryTree(BinaryTree node) {
    // O(n) time | O(d) space d -> depth of tree
    // O(n) time | O(d) space d -> depth of tree
    flatten(node, null, null);
    while (node.left != null) node = node.left;
    return node;
  2. tonymontaro created this gist Apr 16, 2020.
    36 changes: 36 additions & 0 deletions algoexperts-flattenBinaryTree.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,36 @@
    class Program {
    public static BinaryTree flattenBinaryTree(BinaryTree node) {
    // O(n) time | O(d) space d -> depth of tree
    flatten(node, null, null);
    while (node.left != null) node = node.left;
    return node;
    }

    static void flatten(BinaryTree node, BinaryTree left, BinaryTree right) {
    boolean isLeftMost = node.left == null && left != null;
    boolean isRightMost = node.right == null && right != null;
    boolean shouldExploreLeft = node.left != null;
    boolean shouldExploreRight = node.right != null;

    if (isLeftMost) {
    node.left = left;
    left.right = node;
    } else if (shouldExploreLeft) flatten(node.left, left, node);

    if (isRightMost) {
    node.right = right;
    right.left = node;
    } else if (shouldExploreRight) flatten(node.right, node, right);
    }

    // This is the class of the input root. Do not edit it.
    static class BinaryTree {
    int value;
    BinaryTree left = null;
    BinaryTree right = null;

    public BinaryTree(int value) {
    this.value = value;
    }
    }
    }