Observations

The number of nodes in the left and right subtrees of a binary tree differ by at most 1.

Every node in the left subtree of a binary search tree is less than or equal to the value of the parent (root) node.

Every node in the right subtree of a binary search tree is greater than the value of the parent (root) node.

The root node of a balanced binary search tree is the middle value in the tree’s set of values.

The middle element of a sorted array corresponds to the root node of a binary search tree.

Code

import java.util.*;

/*
*	Given an array of distinct integers, use them to build a balanced binary search tree.
*/
class Solution {
	/*
	*	Node class for constructing a binary tree of integers.
	*/
	class Node {
		private int data;
		public Node left;
		public Node right;
		 	
		public Node(int data) {
			this.data = data;
			this.left = null;
			this.right = null;
		}
	}
	
	/*
	*	Build a binary search tree for a given range of indices. Called by {@link Solution#arrayToBalancedBST}.
	*	
	*	@param int[] numbers An array of distinct integers sorted in ascending order.
	*	@param int start The starting index for the smallest element in the BST.
	*	@param int end The ending index for the largest element in the BST.
	*
	*	@return Node The root of the BST constructed from the given range of indices.
	*/
	private Node build(int[] numbers, int start, int end) {
		System.err.println("Called build for range " + start + " to " + end);
		
		Node root = null;
		
		// If we can create at least one new node for the given range of indices
		if (start <= end) {
			// Get index of new parent/root node
			int mid = (start + end) / 2;
			root = new Node(numbers[mid]);
			System.err.println("Created Node: " + root.data);
			
			// This isn't super necessary but it saves 2 extra function 
			// calls for each leaf node that would return null
			if (start != end) { // Comment this out to see the unnecessary calls
				root.left = build(numbers, start, mid - 1);
				root.right = build(numbers, mid + 1, end);
			}
		}
		
		// Return the new root
		return root;
	}
	
	/*
	*	@return The root of a balanced binary search tree
	*/
	public Node arrayToBalancedBST(int[] numbers) {
		// Sort numbers in ascending order
		Arrays.sort(numbers);
		
		return build(numbers, 0, numbers.length - 1);
	}
	
	/*
	*	Prints an in-order tree traversal.
	*/
	public void inOrder(Node root) {
		// Traverse all the way left
		if (root.left != null) {
			inOrder(root.left);
		}
		
		// Print current node
		System.out.println("Traversed Node: " + root.data);
		
		// Continue traversal with right subtree
		if (root.right != null) {
			inOrder(root.right);
		}
	}
	
	/*
	*	Driver function
	*/
	public static void run() {
		Solution solution = new Solution();
		int[] numbers = {5, 4, 7, 3, 2, 1, 6};
		Node root = solution.arrayToBalancedBST(numbers);
		solution.inOrder(root);
	}
	
	public static void main(String[] args) {
		Solution.run();
	}
}

Objective

Given an array of integers and a value, find a pair of distinct elements in the array that sum to the given value.

Observations

We want to find two elements satisfying:
element1 + element2 = value
We need to find element1 and element2 within the array that satisfy the equation above (if they even exist), but value is known.
We can rearrange this equation as:
- element1 = value - element2
- element2 = value - element1

Code

import java.util.*;

class Solution {
		
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value the pair of elements must sum to
	*
	*	@return The distinct pair of VALUES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumValues(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{nums[i], nums[index]};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
	
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value 
	*
	*	@return The distinct pair of INDICES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumIndices(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{i, index};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
}

atebitbyte

Tag Archives: Arrays

Convert an Array of Integers to a BST

Objective

Observations

Find Two Numbers That Sum to a Given Value

Objective

Observations