[Data Structure] #datastructure

binarytree.py

from queue import Queue

class Node(object):
    def __init__(self, data = None, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

class BinaryTree(object):
    def __init__(self, data=None):
        self.size = 0
        self.root = None
        if data != None:
            self.size += 1
            self.root = Node(data)

    def add(self, data, node=None):
        if node == None:
            if self.root == None:
                self.size += 1
                self.root = Node(data)
                return
            else:
                self.add(data, self.root)
                return

        if data < node.data:
            if node.left == None:
                self.size += 1
                node.left = Node(data)
                return
            else:
                self.add(data, node.left)
                return

        if data > node.data:
            if node.right == None:
                self.size += 1
                node.right = Node(data)
                return
            else:
                self.add(data, node.right)
                return

    def delete(self, data):
        self.root = self.__delete(self.root, data)

    def find(self, data):
        curr = self.root
        while curr != None:
            if data == curr.data:
                return curr
            if data < curr.data :
                curr = curr.left
                continue
            if data > curr.data:
                curr = curr.right
        return curr

    def has(self, data):
        return self.find(data) != None

    def min(self):
        if self.root == None:
            return None
        curr = self.root
        while curr.left != None:
            curr = curr.left
        return curr.data

    def max(self):
        if self.root == None:
            return None
        curr = self.root
        while curr.right != None:
            curr = curr.right
        return curr.data

    def count(self):
        return self.size

    def items(self, mode='in'):
        if mode == 'lev':
            return self.__level_order(self.root)
        if mode == 'pre':
            return self.__pre_order(self.root)
        if mode == 'in':
            return self.__in_order(self.root)
        if mode == 'pos':
            return self.__post_order(self.root)

    def __delete(self, node, data):
        if node == None:
            return None
        if data == node.data:
            if node.left == None and node.right == None:
                self.size -= 1
                return None
            if node.left == None:
                self.size -= 1
                return node.right
            if node.right == None:
                self.size -= 1
                return node.left
            # Go rigth and follow left to swap data with the
            # left most leaf node and delete it
            temp = node.right
            while temp.left != None:
                temp = temp.left
            node.data = temp.data
            node.right = self.__delete(node.right, temp.data)
        if data < node.data :
            node.left = self.__delete(node.left, data)
            return node
        if data > node.data:
            node.right = self.__delete(node.right, data)
            return node

    def __height(self):
        pass

    def __level_order(self, root):
        q = Queue()
        q.enqueue(root)
        while q.count() != 0:
            node = q.dequeue()
            yield node.data
            if node.left != None:
                q.enqueue(node.left)
            if node.right != None:
                q.enqueue(node.right)

    def __pre_order(self, curr):
        if curr != None:
            yield curr.data
            yield from self.__pre_order(curr.left)
            yield from self.__pre_order(curr.right)

    def __in_order(self, curr):
        if curr != None:
            yield from self.__in_order(curr.left)
            yield curr.data
            yield from self.__in_order(curr.right)

    def __post_order(self, curr):
        if curr != None:
            yield from self.__post_order(curr.left)
            yield from self.__post_order(curr.right)
            yield curr.data

invertBinaryTree.py

def invertBinaryTree(self, root):
  	if tree == None:
  		return 
  	temp = tree.left
  	tree.left = tree.right
  	tree.right = temp
  	self.invertBinaryTree(tree.left)
  	self.invertBinaryTree(tree.right)

reverseStackWithoutExtraDs.java

/*
Given a stack, reverse the items without creating any additional data structures.
reverse(1->2->3) = 3->2->1
*/

public Stack<Integer> reverse(Stack<Integer> stack) {
    if (stack.isEmpty()) return stack;
    int temp = stack.pop();
    reverse(stack);
    insertAtBottom(stack, temp);
    return stack;
}
 
private void insertAtBottom(Stack<Integer> stack, int x) {
    if (stack.isEmpty()) {
       stack.push(x);
       return;
    }
 
    int temp = stack.pop();
    insertAtBottom(stack, x);
    stack.push(temp);
}

stackWithArray.java

/*
Implement N > 0 stacks using a single array to store all stack data (you may use auxiliary arrays in your stack object, but all of the objects in all of the stacks must be in the same array). No stack should be full unless the entire array is full.
N = 3;
capacity = 10;
Stacks stacks = new Stacks(N, capacity);
stacks.put(0, 10);
stacks.put(2, 11);
stacks.pop(0) = 10;
stacks.pop(2) = 11;
*/

public class Stacks {
 
    int[] topOfStack;
    int[] stackData;
    int[] nextIndex;
 
    int nextAvailable = 0;
 
    public Stacks(int numStacks, int capacity) {
        topOfStack = new int[numStacks];
        for (int i = 0; i < topOfStack.length; i++) {
            topOfStack[i] = -1;
        }
        stackData = new int[capacity];
        nextIndex = new int[capacity];
        for (int i = 0; i < nextIndex.length - 1; i++) {
            nextIndex[i] = i+1;
        }
        nextIndex[nextIndex.length - 1] = -1;
    }
 
    public void push(int stack, int value) {
        if (stack < 0 || stack >= topOfStack.length) {
            throw new IndexOutOfBoundsException();
        }
 
        if (nextAvailable < 0) return;
 
        int currentIndex = nextAvailable;
        nextAvailable = nextIndex[currentIndex];
        stackData[currentIndex] = value;
        nextIndex[currentIndex] = topOfStack[stack];
        topOfStack[stack] = currentIndex;
    }
 
    public int pop(int stack) {
        if (stack < 0 || stack >= topOfStack.length 
              || topOfStack[stack] < 0) {
            throw new IndexOutOfBoundsException();
        }
 
        int currentIndex = topOfStack[stack];
        int value = stackData[currentIndex]; 
        topOfStack[stack] = nextIndex[currentIndex];
        nextIndex[currentIndex] = nextAvailable;
        nextAvailable = currentIndex;
        return value;
    }
}

treeUtils.py

def treeHeight(root):
	if root is None:
		return 0
	return 1 + max( treeHeight(root.left), treeHeight(root.right))

def preOrder(root):
	if root is None:
		return

	print(root.data)
	preOrder(root.left)
	preOrder(root.right)

def preOderLoop(root):
	stack = [root]
	while stack :
		it = stack.pop()
		print(it)
		stack.push(it.left)
		stack.push(it.right)

def inOrder(root):
	if root is None:
		return
	
	preOrder(root.left)
	print(root.data)
	preOrder(root.right)

def postOrder(root):
	if root is None:
		return

	preOrder(root.left)
	preOrder(root.right)
	print(root.data)

def lowestCommonAncestor(root, a, b):
	while root is not None:
		val = root.data
		if val > a && val > b:
			root = root.left
		elif val < a && val < b:
			root = root.right
		else:
			return root

	return None

def rotateRight(oldRoot):
	newRoot = oldRoot.left
	oldRoot.left = newRoot.right
	newRoot.right = oldRoot
	return newRoot