Trimming a binary tree

Trimming a binary tree

download

Code to trim a binary tree, between two boundary inputs.

public class TrimBinarySearchTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    
    TreeNode start = null;
    boolean z = false;

    public TreeNode trimBST(TreeNode root, int L, int R) {
        _trimBST(root, L, R, null);
        return start;
    }

    private boolean _trimBST(TreeNode node, int L, int R, TreeNode parent) {
        boolean found = false;
        if (node == null) {
            return found;
        }
        if (node.val >= L && node.val <= R) {
            found = true;
            if (parent == null) {
                start = node;
            } else {
                if (node.val >= parent.val) {
                    parent.right = node;
                } else {
                    parent.left = node;
                }
            }
            _trimBST(node.left, L, R, node);
            _trimBST(node.right, L, R, node);
        } else {
            boolean foundl = false;
            boolean foundr = false;
            if (node.left != null) {
                foundl = _trimBST(node.left, L, R, parent);
            }
            if (node.right != null) {
                foundr = _trimBST(node.right, L, R, parent);
            }
            if (node.left == null && node.right == null) {
                if (parent != null) {
                    if (node == parent.left) {
                        parent.left = null;
                    }
                    if (node == parent.right) {
                        parent.right = null;
                    }
                }
            }
            if (!foundl && !foundr) {
                if (parent != null) {
                    if (node == parent.left) {
                        parent.left = null;
                    }
                    if (node == parent.right) {
                        parent.right = null;
                    }
                }
            }
        }
        return found;
    }
}download
Advertisements
READ  Cloning a graph

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Terms of Use | Privacy Policy 
2018-2019 © eXitDiscount