<file_sep>import io
import unittest
import unittest.mock

from p01 import print_depth


class TestProblem01(unittest.TestCase):

    @unittest.mock.patch('sys.stdout', new_callable=io.StringIO)
    def assert_stdout(self, data, expected_output, mock_stdout):
        print_depth(data)
        self.assertEqual(mock_stdout.getvalue(), expected_output)

    def test01(self):
        a = {
            "key1": 1,
            "key2": 2,
            "key3": {
                "key4": 3
            }
        }
        self.assert_stdout(a, 'key1 1\nkey2 1\nkey3 1\nkey4 2\n')

    def test02(self):
        a = {
            "key1": 1,
            "key2": {
                "key3": 1,
                "key4": {
                    "key5": 4
                }
            }
        }
        self.assert_stdout(a, "key1 1\nkey2 1\nkey3 2\nkey4 2\nkey5 3\n")


if __name__ == '__main__':
    unittest.main()
<file_sep>import unittest
from p03 import *


class TestProblem03(unittest.TestCase):

    def test_01(self):
        self.assertEqual(lca(n6, n7), 3)

    def test_02(self):
        self.assertEqual(lca(n3, n7), 3)

    def test_03(self):
        self.assertEqual(lca(n1, n2), 1)

    def test_04(self):
        self.assertEqual(lca(n1, n7), 1)

    def test_05(self):
        self.assertEqual(lca(n8, n5), 2)

    def test_06(self):
        self.assertEqual(lca(n8, n8), 8)

    def test_07(self):
        self.assertEqual(lca(n3, n7), 3)

    def test_08(self):
        self.assertEqual(lca(n1, n1), 1)


if __name__ == '__main__':
    unittest.main()
<file_sep>import io
import unittest
import unittest.mock

from p02 import print_depth, person_b


class TestProblem02(unittest.TestCase):

    @unittest.mock.patch('sys.stdout', new_callable=io.StringIO)
    def assert_stdout(self, data, expected_output, mock_stdout):
        print_depth(data)
        self.assertEqual(mock_stdout.getvalue(), expected_output)

    def test_01(self):

        a = {
            "key1": 1,
            "key2": {
                "key3": 1,
                "key4": {
                    "key5": 4,
                    "user": person_b,
                    "key6": {
                        "key7": 4
                    }
                }
            }
        }

        self.assert_stdout(a, 'key1 1\nkey2 1\nkey3 2\nkey4 2\nkey5 3\nuser: 3\nfirst_name: 4\nlast_name: 4\n'
                           + 'father: 4\nfirst_name: 5\nlast_name: 5\nfather: 5\nkey6 3\nkey7 4\n')

    def test_02(self):
        a = {
            "key1": 1,
            "key2": {
                "key3": 1,
                "key4": {
                    "key5": 4
                }
            }
        }
        self.assert_stdout(a, 'key1 1\nkey2 1\nkey3 2\nkey4 2\nkey5 3\n')

    def test_03(self):
        a = {
            "key1": 1,
            "key2": 2,
            "key3": {
                "key4": 3
            }
        }

        self.assert_stdout(a, 'key1 1\nkey2 1\nkey3 1\nkey4 2\n')


if __name__ == '__main__':
    unittest.main()
<file_sep>'''
Time and Memory complexity analysis

-->Time complexity<--

* every step program prints one element until the total number of keys,

so total costs of the program as follows: 1+2+3+.....+n

Hence time complexity of this program is linear or O(n)

-->Space/Memory<--

* The recursive calls of this program does not save its state to the Stack, But in order to create 
Dictionary it costs linear space which is proportional to number of keys
So we can consider the Space complexity of this program is O(n)

'''


class Person(object):
    def __init__(self, first_name, last_name, father):
        self.first_name = first_name
        self.last_name = last_name
        self.father = father


person_a = Person("User", None, None)
person_b = Person("User", "2", person_a)


test = {
    "key1": {
        "key2": {
            "key3": 1
        }
    },
    "key4": {
        "key5": {
            "key6": 2
        }
    },
    "key7": {
        "key8": {
            "key9": 3
        }
    }
}


a = {
    "key1": 1,
    "key2": {
        "key3": 1,
        "key4": {
            "key5": 4,
            "user1": person_b,
            "key6": {
                "key7": 4,
            }
        }
    }
}


# Print function when it's an instance of Person

def print_for_person(k, depth):
    print(str(k)+': '+str(depth))


# Print function when it's an instance of dictionary

def print_for_dict(k, depth):
    print(str(k)+' '+str(depth))


# Driver function

def print_depth(data, depth=1):

    # If value of a key is Instance of Person

    if isinstance(data, Person):
        for k, v in vars(data).items():

            # Handling all of the properties of Person instance
            if isinstance(v, Person):
                print_for_person(k, depth)
                print_depth(v, depth+1)

            # Handling None property of Person instance
            else:
                print_for_person(k, depth)

    # When value of a key is Instance of dictionary

    else:
        for k, v in data.items():

            # A value of dictionary can be instance of either dict or Person

            # When value of a key is instance of dict

            if isinstance(v, dict):

                print_for_dict(k, depth)
                print_depth(v, depth+1)

            # When value of a key is instance of Person

            elif isinstance(v, Person):
                print_for_person(k, depth)
                print_depth(v, depth+1)

            # If value of a key is not another dict or Person instance
            else:
                print_for_dict(k, depth)


# print_depth(person_b)
<file_sep>'''
Time and Memory complexity analysis

-->Time complexity<--

* every step program prints one element until the total number of keys,

so total costs of the program as follows: 1+2+3+.....+n

Hence time complexity of this program is linear or O(n)

-->Space/Memory<--

* The recursive calls of this program does not save its state to the Stack, But in order to create 
Dictionary it costs linear space which is proportional to number of keys
So we can consider the Space complexity of this program is O(n)

'''


def print_depth(data, depth=1):
    for key in data:
        print(key, depth)
        if isinstance(data[key], dict):
            print_depth(data[key], depth+1)


# print_depth(a)
<file_sep>'''
Time and Memory complexity analysis

-->Time complexity<--

* For constructing the binary tree total cost is numbers of nodes "n"
so overall time complexity O(n)

* For getting the paths to root node of two given nodes is equal to the numbers of 
nodes to the root, In worst case it will be height of the tree O(h)+O(h)

* and selecting least common node between two Stacks cost would be in worst case O(h), where
h height of the tree

-> Overall time complexity in worst case is O(n)

-->Space/Memory<--

* For constructing the binary tree total Space complexity in worst case in O(n)
where n is number of nodes of the tree
* and Space complexity of storing values to Stack is propotional to height of the tree 
in worst case so we can consider O(h)

-> Overall Space complexity of this problem is O(n)


'''


from collections import deque


class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent


# This function returns all of the nodes from target node to the root node

def pathToRoot(Node):

    paths = deque()

    currentNode = Node

    while currentNode.parent:
        paths.append(currentNode.value)
        currentNode = currentNode.parent
    paths.append(currentNode.value)

    return paths


def lca(node1, node2):

    # Getting paths of two given nodes

    paths_of_node1 = pathToRoot(node1)
    paths_of_node2 = pathToRoot(node2)

    # Finding out the least common value between two paths

    lca_of_two = None
    while paths_of_node1 and paths_of_node2:
        pop1 = paths_of_node1.pop()
        pop2 = paths_of_node2.pop()

        if pop1 == pop2:
            lca_of_two = pop1
        else:
            break
    return lca_of_two


# inserting nodes

n1 = Node(1, None)
n2 = Node(2, n1)
n3 = Node(3, n1)
n4 = Node(4, n2)
n5 = Node(5, n2)
n6 = Node(6, n3)
n7 = Node(7, n3)
n8 = Node(8, n4)
n9 = Node(9, n4)

# result = lca(n3, n7)
# print(result)
<file_sep># Instruction for Unittesting

## For testing Task 01

$ python3 -m unittest tests/test_p01.py

## For testing Task 02

$ python3 -m unittest tests/test_p02.py

## For testing Task 03

$ python3 -m unittest tests/test_p03.py
