#   A simple complete binary tree implementation with DFS methods


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

    def getData(self):
        return self.data

    def setData(self, newData):
        return self.data

    def getLeftChild(self):
        return self.left

    def setLeftChild(self, newData):
        self.left = newData

    def getRightChild(self):
        return self.right

    def setRightChild(self, newData):
        self.right = newData


class BTree:
    def __init__(self, newData):
        self.root = Node(newData)

    def isEmpty(self):
        return self.root is None

    def empty(self):
        self.root = None

    def insert(self, newData):
        if self.root is None:
            self.root = Node(newData)
        else:
            self._insert(newData, self.root)

    def _insert(self, newData, node):
        if newData < node.getData():
            if node.getLeftChild() is not None:
                self._insert(newData, node.getLeftChild())
            else:
                node.setLeftChild(Node(newData))
        else:
            if node.getRightChild() is not None:
                self._insert(newData, node.getRightChild())
            else:
                node.setLeftChild(Node(newData))

    def find(self, data):
        if self.root is not None:
            return self._find(data, self.root)
        else:
            return False

    def _find(self, data, node):
        if data == node.getData():
            return node.getData()
        elif data < node.getData() and node.getLeftChild() is not None:
            self._find(data, node.getLeftChild())
        elif data > node.getData() and node.getRightChild() is not None:
            self._find(data, node.getRightChild())

    def inOrder(self, root):
        if root:
            self.inOrder(root.getLeftChild())
            print(root.getData)
            self.inOrder(root.getRightChild())

    def postOrder(self, root):
        if  root:
            self.postOrder(root.getLeftChild())
            self.postOrder(root.getRightChild())
            print(root.getData)

    def preOrder(self, root):
        if root:
            print(root.getData)
            self.preOrder(root.getLeftChild())
            self.preOrder(root.getRightChild())